QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882600#3680. 序列染色_rey100 ✓71ms16172kbC++172.0kb2025-02-05 09:40:112025-02-05 09:40:11

Judging History

This is the latest submission verdict.

  • [2025-02-05 09:40:11]
  • Judged
  • Verdict: 100
  • Time: 71ms
  • Memory: 16172kb
  • [2025-02-05 09:40:11]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using lli = long long;

template<int MOD>
class modint {
	int val;

public:
	modint(lli val = 0) : val (val % MOD) { }

	modint<MOD> operator+(const modint<MOD> &other) { return modint(val + other.val); }
	modint<MOD> operator-(const modint<MOD> &other) { return modint(val - other.val + MOD); }
	modint<MOD> operator*(const modint<MOD> &other) { return modint(1LL*val*other.val); }
	int operator()() { return val; }

	modint<MOD> pot(int n) {
		if (n == 0) return 1;

		auto x = pot(n/2);
		x = x*x;

		if (n%2 == 0) return x;
		return *this * x;
	}
};

using mint = modint<1000000007>;

int main() {
	int n, k;
	cin >> n >> k;

	if (k >= n) {
		cout << "0\n";
		return 0;
	}

	string s;
	cin >> s;

	vector<mint> dpB(n);

	{
		int cnt = 0; int cntW = 0; mint sum;
		for (int i = 0; i < k; ++i)
			if (s[i] == 'W') ++cntW;

		for (int i = k-1; i < n; ++i) {
			if (cntW == 0 && (i == k-1 || s[i - k] != 'B')) 
				dpB[i] = mint(2).pot(cnt) - sum;

			if (i - k >= 0) {
				if (s[i - k] == 'X') { ++cnt; sum = sum*mint(2); }
				sum = sum + dpB[i - k];
			}
			if (s[i - (k - 1)] == 'W') --cntW;
			if (i < n && s[i + 1] == 'W') ++cntW;
		}
	}

	vector<mint> dpW(n);

	{
		int cnt = 0; int cntB = 0; mint sum;
		for (int i = n - 1; i >= n - k; --i)
			if (s[i] == 'B') ++cntB;

		for (int i = n - k; i >= 0; --i) {
			if (cntB == 0 && (i == n - k || s[i + k] != 'W')) 
				dpW[i] = mint(2).pot(cnt) - sum;

			if (i < n - k) {
				if (s[i + k] == 'X') { ++cnt; sum = sum*mint(2); }
				sum = sum + dpW[i + k];
			}
			if (s[i + (k - 1)] == 'B') --cntB;
			if (i >= 0 && s[i - 1] == 'B') ++cntB;
		}
	}

	vector<mint> sumW(n + 1);

	for (int i = n-1; i >= 0; --i) 
		if (s[i] == 'X') sumW[i] = sumW[i + 1]*mint(2) + dpW[i];
		else sumW[i] = sumW[i + 1] + dpW[i];
	
	mint ans;
	for (int i = 0; i < n; ++i)
		ans = ans + dpB[i]*sumW[i + 1];

	cout << ans() << "\n";
}

详细


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 3584kb

input:

1 1000000
X


output:

0

result:

ok single line: '0'

Test #2:

score: 10
Accepted
time: 0ms
memory: 3584kb

input:

20 4
XXXXXXXXXXXXXXXXXXXX


output:

108155

result:

ok single line: '108155'

Test #3:

score: 10
Accepted
time: 1ms
memory: 3584kb

input:

2000 200
BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...

output:

590565731

result:

ok single line: '590565731'

Test #4:

score: 10
Accepted
time: 1ms
memory: 3584kb

input:

2000 100
WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...

output:

313979285

result:

ok single line: '313979285'

Test #5:

score: 10
Accepted
time: 1ms
memory: 3584kb

input:

2000 100
XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...

output:

358862528

result:

ok single line: '358862528'

Test #6:

score: 10
Accepted
time: 56ms
memory: 13052kb

input:

765432 5000
WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...

output:

74325182

result:

ok single line: '74325182'

Test #7:

score: 10
Accepted
time: 65ms
memory: 14572kb

input:

876543 5000
WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...

output:

786550221

result:

ok single line: '786550221'

Test #8:

score: 10
Accepted
time: 71ms
memory: 15972kb

input:

1000000 10000
WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...

output:

627927296

result:

ok single line: '627927296'

Test #9:

score: 10
Accepted
time: 70ms
memory: 16172kb

input:

1000000 20000
XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...

output:

412860887

result:

ok single line: '412860887'

Test #10:

score: 10
Accepted
time: 69ms
memory: 16168kb

input:

1000000 50000
WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...

output:

773406112

result:

ok single line: '773406112'