제출 #436533

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
436533		codebuster_10	Genetics (BOI18_genetics)	C++17	100 / 100	1138 ms	153960 KiB

genetics

#include <bits/stdc++.h>
using namespace std;

















/**
 * Description :- modular arithmetic operations
 * Source :- https://codeforces.com/contest/1342/submission/78409946
 * Verification:- https://open.kattis.com/problems/modulararithmetic
 */

template<const int &MOD>
struct _m_int {
  int val;

  _m_int(int64_t v = 0) {
    if(v < 0) v = v % MOD + MOD;
    if(v >= MOD) v %= MOD;
    val = v;
  }

  static int inv_mod(int a, int m = MOD) {
    // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
    int g = m, r = a, x = 0, y = 1;

    while(r != 0) {
      int q = g / r;
      g %= r; swap(g, r);
      x -= q * y; swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  // wont work if we use #define int int64_t
  // explicit operator int() const { return val; }
  explicit operator int64_t() const { return val; }

  _m_int& operator+=(const _m_int &other) {
    val -= MOD - other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  _m_int& operator-=(const _m_int &other) {
    val -= other.val;
    if(val < 0) val += MOD;
    return *this;
  }

  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
#if !defined(_WIN32) || defined(_WIN64)
    return x % m;
#endif
    // Optimized mod for Codeforces 32-bit machines.
    // x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit unsigned int.
    unsigned x_high = x >> 32, x_low = (unsigned) x;
    unsigned quot, rem;
    asm("divl %4\n"
      : "=a" (quot), "=d" (rem)
      : "d" (x_high), "a" (x_low), "r" (m));
    return rem;
  }

  _m_int& operator*=(const _m_int &other) {
    val = fast_mod((uint64_t) val * other.val);
    return *this;
  }

  _m_int& operator/=(const _m_int &other) {
    return *this *= other.inv();
  }

  friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }
  friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }
  friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }
  friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }

  _m_int& operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }

  _m_int& operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }

  // wont work if we use #define int int64_t
  // _m_int operator++(int) { _m_int before = *this; ++*this; return before; }
  // _m_int operator--(int) { _m_int before = *this; --*this; return before; }

  _m_int operator-() const {
    return val == 0 ? 0 : MOD - val;
  }

  bool operator==(const _m_int &other) const { return val == other.val; }
  bool operator!=(const _m_int &other) const { return val != other.val; }

  _m_int inv() const {
    return inv_mod(val);
  }

  _m_int pow(int64_t p) const {
    if(p < 0)	return inv().pow(-p);
    _m_int a = *this, result = 1;
    while(p > 0) {
      if(p & 1)	result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }

  friend ostream& operator<<(ostream &os, const _m_int &m) {
    return os << m.val;
  }
};

extern const int MOD = int(1e9) + 7;
using mint = _m_int<MOD>;

#define rand __rand

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1));
int rand(int L = 0,int R = int(1e9)){
  return uniform_int_distribution<int>(L,R)(rng) ;
}



const int HASH_COUNT = 2;
const int BASE[] = {rand(0.1 * MOD, 0.9 * MOD), rand(0.1 * MOD, 0.9 * MOD)};

const string LETTERS = "ATGC";
const int LETTERS_SIZE = 4;







































signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  int N,M,K;
  cin >> N >> M >> K;
  
  K = M-K; // number of same chars.
	
	
	vector<mint> pow[2];
	
	for(int i = 0; i < HASH_COUNT; ++i){
		for(int j = 0; j < N; ++j){
			pow[i].push_back(mint(BASE[i]).pow(j));
		}
	}
	  
  vector<string> s(N);
  for(int i = 0; i < N; ++i) cin >> s[i];
  
  vector<vector<mint>> a[HASH_COUNT];
  
  for(int i = 0; i < HASH_COUNT; ++i){
  	a[i] = vector<vector<mint>>(M,vector<mint>(N));
  }
  
  vector<mint> total[HASH_COUNT][LETTERS_SIZE];
  
  for(int j = 0; j < HASH_COUNT; ++j){
  	for(int  i = 0; i < LETTERS_SIZE; ++i){
  		total[j][i] = vector<mint> (M);
  	}
  }
  
  // value if a[i][j] is activated.
  for(int i = 0; i < M; ++i){
  	for(int j = 0; j < N; ++j){
  		for(int k = 0; k < HASH_COUNT; ++k){
  			a[k][i][j] = pow[k][j];
  			for(int u = 0; u <  LETTERS_SIZE; ++u) if(LETTERS[u] == s[j][i]){
  				total[k][u][i] += a[k][i][j];
  			}
  		}
  	}
  }
  
  mint NEED[HASH_COUNT];
  for(int i = 0; i < N; ++i){
  	for(int j = 0; j < HASH_COUNT; ++j){
  		NEED[j] += K * pow[j][i];
  	}
  }
  
  for(int i = 0; i < N; ++i){
  	mint need[HASH_COUNT];
  	for(int j = 0; j < HASH_COUNT; ++j){
  		need[j] = NEED[j] + (M - K) * pow[j][i];
  	}
  	
  	for(int j = 0; j < M; ++j){
  		for(int k = 0; k < HASH_COUNT; ++k){
  			for(int u = 0; u <  LETTERS_SIZE; ++u) if(LETTERS[u] == s[i][j]){
  				need[k] -= total[k][u][j];
  			}
  		}
  	}
  	
  	bool ok = true;
  	for(int j = 0; j < HASH_COUNT; ++j){
  		ok &= need[j] == mint(0);
  	}
  	
  	if(ok){
  		cout << i + 1; exit(0);
  	}
  }
  
  assert(false);
}

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26