#include<bits/stdc++.h>
using namespace std;
const int const1 = 1e9 + 7;
const int const2 = 998244353;
vector <vector <vector <int> > > g;
vector <vector <bool> > used;
vector <vector <int> > dist;
void dfs(int a, int b)
{
used[a][b] = 1;
if(a == 0)
{
dist[a][b] = 1;
return;
}
for(int i = 0; i < g[a][b].size(); i++)
{
int to = g[a][b][i];
if(i == 0 || to != g[a][b][i - 1])
{
if(!used[a - 1][to])
{
dfs(a - 1, to);
}
dist[a][b] += dist[a - 1][to];
if(dist[a][b] >= const1)
{
dist[a][b] -= const1;
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, k;
cin >> n >> k;
used.resize(n, vector <bool> (k));
dist.resize(n, vector <int> (k));
g.resize(n, vector <vector <int> > (k));
vector <int> Pow(n + 1), Pow1(n + 1);
Pow[0] = 1;
Pow1[0] = 1;
for(int i = 1; i <= n; i++)
{
Pow1[i] = 1LL * Pow1[i - 1] * 27 % const2;
Pow[i] = 1LL* Pow[i - 1] * 27 % const1;
}
vector <vector <pair <int, int> > > hashes(n);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < k; j++)
{
string s;
cin >> s;
int hash1 = 0;
int hash2 = 0;
for(int p = 0; p < i + 1; p++)
{
hash1 = (1LL * hash1 * 27 + s[p] - 'a' + 1) % const1;
hash2 = (1LL * hash2 * 27 + s[p] - 'a' + 1) % const2;
}
hashes[i].push_back({hash1, hash2});
}
sort(hashes[i].begin(), hashes[i].end());
}
for(int i = 0; i < n - 1; i++)
{
for(int j = 0; j < k; j++)
{
vector <pair <int, int> > mass1;
for(int a = 1; a <= 26; a++)
{
int hash2 = 1LL * (hashes[i][j].first * 27 + a) % const1;
int hash3 = 1LL * (hashes[i][j].second * 27 + a) % const2;
mass1.push_back({hash2, hash3});
hash2 = 1LL * (hashes[i][j].first + a * Pow[i + 1]) % const1;
hash3 = 1LL * (hashes[i][j].second + a * Pow1[i + 1]) % const2;
mass1.push_back({hash2, hash3});
}
sort(mass1.begin(), mass1.end());
int it = 0;
for(int d = 0; d < k; d++){
while(it < mass1.size() && (mass1[it].first < hashes[i + 1][d].first ||
(mass1[it].first == hashes[i + 1][d].first && mass1[it].second < hashes[i + 1][d].second)))
{
it++;
}
if(it != mass1.size() && mass1[it] == hashes[i + 1][d])
{
g[i + 1][d].push_back(j);
}
}
}
}
for(int i = 0; i < n; i++)
{
for(int j = 0; j < k; j++)
{
sort(g[i][j].begin(), g[i][j].end());
}
}
int ans = 0;
for(int i = 0;i < k; i++)
{
dfs(n - 1, i);
ans += dist[n - 1][i];
if(ans >= const1)
{
ans -= const1;
}
}
cout << ans;
return 0;
}
Compilation message
trener.cpp: In function 'void dfs(int, int)':
trener.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[a][b].size(); i++)
~~^~~~~~~~~~~~~~~~
trener.cpp: In function 'int main()':
trener.cpp:85:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(it < mass1.size() && (mass1[it].first < hashes[i + 1][d].first ||
~~~^~~~~~~~~~~~~~
trener.cpp:90:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(it != mass1.size() && mass1[it] == hashes[i + 1][d])
~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
16 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
