QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#486966 | #3680. 序列染色 | KiharaTouma | 100 ✓ | 24ms | 36052kb | C++23 | 1.4kb | 2024-07-22 14:17:41 | 2024-07-22 14:17:42 |
Judging History
answer
//qoj3680
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const ll P = 1e9 + 7;
int n, k;
ll f[N], g[N], F[N], G[N];
char s[N];
#define cl(x) ((x) == 'X' ? 2 : 1)
int main(){
scanf("%d%d", &n, &k);
scanf("%s", s+1);
f[0] = g[n+1] = 1;
for(int i = 1, la = 0; i <= n; ++ i){
if(s[i] == 'W'){
la = i;
}
if(la >= i - k + 1){
f[i] = f[i-1] * cl(s[i]) % P;
} else {
int v = s[i-k] == 'B' ? 0 : i==k ? 1 : f[i-k-1];
f[i] = (P + f[i-1] * cl(s[i]) - v) % P;
}
}
for(int i = n; i >= 1; -- i){
f[i] = s[i] == 'B' ? 0 : f[i-1];
}
for(int i = 1, la = 0; i <= n; ++ i){
if(s[i] == 'W'){
la = i;
}
if(la < i - k + 1){
F[i] = f[i-k];
}
}
for(int i = n, la = n+1; i >= 1; -- i){
if(s[i] == 'B'){
la = i;
}
if(la <= i + k - 1){
g[i] = g[i+1] * cl(s[i]) % P;
} else {
int v = s[i+k] == 'W' ? 0 : n-i+1==k ? 1 : g[i+k+1];
g[i] = (P + g[i+1] * cl(s[i]) - v) % P;
}
}
for(int i = 1; i <= n; ++ i){
g[i] = s[i] == 'W' ? 0 : g[i+1];
}
for(int i = n, la = n+1; i >= 1; -- i){
if(s[i] == 'B'){
la = i;
}
if(la > i + k - 1){
G[i] = g[i+k];
}
}
ll ans = 0, sum = 0;
for(int i = 1; i <= n; ++ i){
sum = (sum * cl(s[i]) + F[i]) % P;
ans = (ans + sum * G[i+1]) % P;
}
printf("%lld\n", ans);
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 8016kb
input:
1 1000000 X
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 1ms
memory: 10104kb
input:
20 4 XXXXXXXXXXXXXXXXXXXX
output:
108155
result:
ok single line: '108155'
Test #3:
score: 10
Accepted
time: 1ms
memory: 10076kb
input:
2000 200 BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...
output:
590565731
result:
ok single line: '590565731'
Test #4:
score: 10
Accepted
time: 0ms
memory: 9996kb
input:
2000 100 WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...
output:
313979285
result:
ok single line: '313979285'
Test #5:
score: 10
Accepted
time: 0ms
memory: 12072kb
input:
2000 100 XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...
output:
358862528
result:
ok single line: '358862528'
Test #6:
score: 10
Accepted
time: 18ms
memory: 34564kb
input:
765432 5000 WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...
output:
74325182
result:
ok single line: '74325182'
Test #7:
score: 10
Accepted
time: 16ms
memory: 35176kb
input:
876543 5000 WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...
output:
786550221
result:
ok single line: '786550221'
Test #8:
score: 10
Accepted
time: 24ms
memory: 36052kb
input:
1000000 10000 WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...
output:
627927296
result:
ok single line: '627927296'
Test #9:
score: 10
Accepted
time: 20ms
memory: 35600kb
input:
1000000 20000 XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...
output:
412860887
result:
ok single line: '412860887'
Test #10:
score: 10
Accepted
time: 24ms
memory: 33988kb
input:
1000000 50000 WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...
output:
773406112
result:
ok single line: '773406112'