QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#486962 | #3680. 序列染色 | KiharaTouma | 20 | 24ms | 36132kb | C++23 | 1.4kb | 2024-07-22 14:07:23 | 2024-07-22 14:07:23 |
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] == 'B' ? 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: 0ms
memory: 8008kb
input:
1 1000000 X
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 0ms
memory: 9980kb
input:
20 4 XXXXXXXXXXXXXXXXXXXX
output:
108155
result:
ok single line: '108155'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 12104kb
input:
2000 200 BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...
output:
838950986
result:
wrong answer 1st lines differ - expected: '590565731', found: '838950986'
Test #4:
score: 0
Wrong Answer
time: 2ms
memory: 10120kb
input:
2000 100 WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...
output:
162619768
result:
wrong answer 1st lines differ - expected: '313979285', found: '162619768'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 10064kb
input:
2000 100 XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...
output:
190807986
result:
wrong answer 1st lines differ - expected: '358862528', found: '190807986'
Test #6:
score: 0
Wrong Answer
time: 19ms
memory: 35484kb
input:
765432 5000 WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...
output:
294775170
result:
wrong answer 1st lines differ - expected: '74325182', found: '294775170'
Test #7:
score: 0
Wrong Answer
time: 22ms
memory: 34680kb
input:
876543 5000 WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...
output:
610572102
result:
wrong answer 1st lines differ - expected: '786550221', found: '610572102'
Test #8:
score: 0
Wrong Answer
time: 24ms
memory: 36132kb
input:
1000000 10000 WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...
output:
889872167
result:
wrong answer 1st lines differ - expected: '627927296', found: '889872167'
Test #9:
score: 0
Wrong Answer
time: 24ms
memory: 35704kb
input:
1000000 20000 XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...
output:
384505476
result:
wrong answer 1st lines differ - expected: '412860887', found: '384505476'
Test #10:
score: 0
Wrong Answer
time: 20ms
memory: 33968kb
input:
1000000 50000 WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...
output:
970559900
result:
wrong answer 1st lines differ - expected: '773406112', found: '970559900'