QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#486966#3680. 序列染色KiharaTouma100 ✓24ms36052kbC++231.4kb2024-07-22 14:17:412024-07-22 14:17:42

Judging History

你现在查看的是最新测评结果

  • [2024-07-22 14:17:42]
  • 评测
  • 测评结果:100
  • 用时:24ms
  • 内存:36052kb
  • [2024-07-22 14:17:41]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'