#include <bits/stdc++.h>
#define MAX 2005000
int N,Q;
using ll = long long;
const ll MOD = 998244353;
typedef std::array<std::array<ll,2>,2> matriz;
matriz mul(matriz a,matriz b){
matriz c={};
for(int i=0;i!=2;++i){
for(int j=0;j!=2;++j){
for(int k=0;k!=2;++k){
c[i][j]=(c[i][j]+(a[i][k]*b[k][j]))%MOD;
}
}
}
return c;
}
int get_num(char ch){
switch(ch){
case 'A': return 0;
case 'G': return 1;
case 'C': return 2;
case 'U': return 3;
}
}
int filhos[MAX][4];
int valor[MAX];
std::string str[MAX];
int freq[MAX];
int cur=2;
int alocar(void){
return cur++;
}
void explora(std::deque<char> dek,std::string bet){
int inicio = 1;
while(dek.size()){
int& ref = filhos[inicio][get_num(dek.front())];
if(!ref)ref=alocar();
inicio=ref;
dek.pop_front();
}
freq[inicio]++;
str[inicio]=bet;
}
std::deque<char> gera_dek(std::string s){
std::deque<char> dek;
for(auto&x:s)dek.push_back(x);
return dek;
}
matriz neutro;
matriz gera_mat(int B){
matriz c={};
c[0][0]=7;
c[1][0]=B+2;
c[1][1]=1;
return c;
}
std::map<matriz,int> mat[MAX*4];
void update(int t,matriz k,int b,int la=0,int ra=MAX-1,int pos=1){
if(ra<t||la>t)return;
mat[pos][k]+=b;
/// std::cout<<"add "<<la<<" "<<ra<<" "<<b<<"\n";
if(la==ra)return;
int m = (la+ra)/2;
update(t,k,b,la,m,pos*2);
update(t,k,b,m+1,ra,(pos*2)+1);
}
int query(int l,int r,matriz k,int la=0,int ra=MAX-1,int pos=1){
if(ra<l||la>r)return 0;
if(la>=l&&ra<=r){
/// std::cout<<"pega "<<la<<" "<<ra<<"\n";
auto ref = mat[pos].find(k);
if(ref==mat[pos].end())return 0;
return ref->second;
}
int m = (la+ra)/2;
return query(l,r,k,la,m,pos*2) + query(l,r,k,m+1,ra,(pos*2)+1);
}
int tamanhos[MAX];
int cur2=1;
int dfs(int node){
if(!node)return 0;
assert(!valor[node]);
///std::cout<<"Nov "<<node<<" "<<cur2<<"!!!\n";
valor[node]=cur2;
int size=1;
if(freq[node]){///Opa!!!
/// std::cout<<"Upd "<<node<<" "<<cur2<<" "<<str[node]<<" "<<freq[node]<<"\n";
matriz bas = neutro;
for(int i=str[node].size()-1;i!=-1;--i){
bas=mul(gera_mat(get_num(str[node][i])),bas);
update(cur2,bas,freq[node]);
///for(int i=0;i!=2;++i){
/// for(int j=0;j!=2;++j){
/// std::cout<<bas[i][j]<<" ";
/// }
/// std::cout<<"\n";
/// }
/// std::cout<<"\n";
}
}
++cur2;
for(int i=0;i!=4;++i){
size+=dfs(filhos[node][i]);
}
tamanhos[node]=size;
/// std::cout<<"Size "<<size<<"->"<<node<<"\n";
return size;
}
int main()
{
neutro[0][0]=neutro[1][1]=1;
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N >> Q;
for(int i=0;i!=N;++i){
std::string s;
std::cin >> s;
explora(gera_dek(s),s);
}
dfs(1);
///Processa
for(int i=0;i!=Q;++i){
std::string l,r;
std::cin >> l >> r;
int inicio = 1;
for(int i=0;i!=l.size();++i){
int p = get_num(l[i]);
inicio = filhos[inicio][p];
if(!inicio){
std::cout<<"0\n";
goto prox;
}
}
/// std::cout<<"ok "<<inicio<<"\n";
{
int tam = tamanhos[inicio],pos=valor[inicio];
/// std::cout<<"! "<<tam<<" "<<pos<<"\n";
matriz bas = neutro;
for(int i=r.size()-1;i!=-1;--i){
bas=mul(gera_mat(get_num(r[i])),bas);
}
/// for(int i=0;i!=2;++i){
/// for(int j=0;j!=2;++j){
/// std::cout<<bas[i][j]<<" ";
/// }
/// std::cout<<"\n";
/// }
/// std::cout<<"\n";
/// std::cout<<pos<<" "<<pos+tam-1<<"<<<\n";
int soma = query(pos,pos+tam-1,bas);
std::cout<<soma<<"\n";
}
prox:{}
}
}
Compilation message
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:128:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i!=l.size();++i){
| ~^~~~~~~~~~
selling_rna.cpp: In function 'int get_num(char)':
selling_rna.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
25 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
440016 KB |
Output is correct |
| 2 |
Correct |
218 ms |
440052 KB |
Output is correct |
| 3 |
Correct |
243 ms |
440012 KB |
Output is correct |
| 4 |
Correct |
240 ms |
440000 KB |
Output is correct |
| 5 |
Correct |
219 ms |
439992 KB |
Output is correct |
| 6 |
Correct |
255 ms |
439960 KB |
Output is correct |
| 7 |
Correct |
220 ms |
440088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1626 ms |
655580 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
270 ms |
440448 KB |
Output is correct |
| 2 |
Correct |
340 ms |
448744 KB |
Output is correct |
| 3 |
Correct |
353 ms |
444908 KB |
Output is correct |
| 4 |
Correct |
283 ms |
440320 KB |
Output is correct |
| 5 |
Correct |
371 ms |
444628 KB |
Output is correct |
| 6 |
Correct |
310 ms |
443068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
440016 KB |
Output is correct |
| 2 |
Correct |
218 ms |
440052 KB |
Output is correct |
| 3 |
Correct |
243 ms |
440012 KB |
Output is correct |
| 4 |
Correct |
240 ms |
440000 KB |
Output is correct |
| 5 |
Correct |
219 ms |
439992 KB |
Output is correct |
| 6 |
Correct |
255 ms |
439960 KB |
Output is correct |
| 7 |
Correct |
220 ms |
440088 KB |
Output is correct |
| 8 |
Execution timed out |
1626 ms |
655580 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
