#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("fast-math")
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int M = 1000100;
const int N = 110;
const int md = int(1e9) + 7;
const int PW = 22;
int a[M], n, m, ans[M], pf[M], bb[M];
bitset<PW> aut[M][N];
int mult(int x, int y) { return (1ll * x * y) % md; }
int sum(int x, int y){
x += y;
if (x >= md)
x -= md;
return x;
}
int sub(int x, int y){
x -= y;
if (x < 0)
x += md;
return x;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> a[i];
bb[i - 1] = a[i];
}
ans[0] = 0;
pf[0] = 0;
for (int i = 1; i < m; i++){
int j = pf[i - 1];
while (j > 0 && bb[i] != bb[j])
j = pf[j - 1];
if (bb[i] == bb[j])
j++;
pf[i] = j;
}
aut[0][a[1]] = 1;
ans[1] = n;
cout << n << '\n';
for (int i = 2; i <= m; i++){
ans[i] = 0;
int id = i - 1;
for (int j = 1; j <= n; j++)
if (j == bb[id]) {
aut[id][j] = i;
} else aut[id][j] = aut[pf[id - 1]][j];
for (int j = 1; j <= n; j++)
if (a[i] != j){
int mx = 0;
for (int po = 0; po < PW; po++)
if (aut[id][j][po])
mx += (1 << po);
ans[i] = sum(ans[i], ans[i - 1]);
ans[i] = sub(ans[i], ans[mx]);
ans[i] = sum(ans[i], 1);
} else {
ans[i] = sum(ans[i], ans[i - 1] + 1);
}
cout << ans[i] << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
512 KB |
Output is correct |
2 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
512 KB |
Output is correct |
2 |
Correct |
0 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
640 KB |
Output is correct |
2 |
Correct |
1 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
768 KB |
Output is correct |
2 |
Correct |
1 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
62 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
108 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
147 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
308 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |