# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
853490 | Trisanu_Das | Genetics (BOI18_genetics) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int P = 9949, Q = int(1e9) + 9;
int n, m, k;
char s[N][N];
int c[5][N], p[N], r;
signed main(){
cin >> n >> m >> k; int t = 1;
for(int i = 1; i <= n; i++){
cin >> s[i];
for(int j = 0; j < m; j++){
s[i][j] = (s[i][j] == 'A' ? 1 : s[i][j] == 'C' ? 2 : s[i][j] == 'G' ? 3 : 4);
c[s[i][j]][j] = (c[s[i][j]][j] + t) % Q;
c[0][j] = (c[0][j] + t) % Q;
}
r = (r + t * k) % Q;
p[i] = t;
t = t * P % Q;
}
for(int i = 1; i <= n; i++){
int t = 0;
for(int j = 0; j < m; j++) t = (t + c[0][j] - c[s[i][j]][j] + Q) % Q;
if((t + p[i] * k) % Q == r){ cout << i << '\n'; return 0; }
}
}