QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#486962#3680. 序列染色KiharaTouma20 24ms36132kbC++231.4kb2024-07-22 14:07:232024-07-22 14:07:23

Judging History

This is the latest submission verdict.

  • [2024-07-22 14:07:23]
  • Judged
  • Verdict: 20
  • Time: 24ms
  • Memory: 36132kb
  • [2024-07-22 14:07:23]
  • Submitted

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'