QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882546#3680. 序列染色_rey20 89ms16192kbC++171.9kb2025-02-05 09:16:032025-02-05 09:16:05

Judging History

This is the latest submission verdict.

  • [2025-02-05 09:16:05]
  • Judged
  • Verdict: 20
  • Time: 89ms
  • Memory: 16192kb
  • [2025-02-05 09:16:03]
  • 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) + 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] != 'B')) 
				dpW[i] = mint(2).pot(cnt) - sum;

			if (i < n - k) {
				if (s[i + k] == 'X') ++cnt;
				sum = sum*mint(2) + 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) 
		sumW[i] = sumW[i + 1]*mint(2) + 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: 1ms
memory: 3584kb

input:

1 1000000
X


output:

0

result:

ok single line: '0'

Test #2:

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

input:

20 4
XXXXXXXXXXXXXXXXXXXX


output:

108155

result:

ok single line: '108155'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3456kb

input:

2000 200
BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...

output:

20575214

result:

wrong answer 1st lines differ - expected: '590565731', found: '20575214'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

input:

2000 100
WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...

output:

118177852

result:

wrong answer 1st lines differ - expected: '313979285', found: '118177852'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3584kb

input:

2000 100
XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...

output:

753605380

result:

wrong answer 1st lines differ - expected: '358862528', found: '753605380'

Test #6:

score: 0
Wrong Answer
time: 69ms
memory: 13208kb

input:

765432 5000
WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...

output:

884811284

result:

wrong answer 1st lines differ - expected: '74325182', found: '884811284'

Test #7:

score: 0
Wrong Answer
time: 83ms
memory: 14576kb

input:

876543 5000
WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...

output:

480380662

result:

wrong answer 1st lines differ - expected: '786550221', found: '480380662'

Test #8:

score: 0
Wrong Answer
time: 89ms
memory: 16192kb

input:

1000000 10000
WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...

output:

449181576

result:

wrong answer 1st lines differ - expected: '627927296', found: '449181576'

Test #9:

score: 0
Wrong Answer
time: 84ms
memory: 16044kb

input:

1000000 20000
XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...

output:

591582891

result:

wrong answer 1st lines differ - expected: '412860887', found: '591582891'

Test #10:

score: 0
Wrong Answer
time: 89ms
memory: 16168kb

input:

1000000 50000
WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...

output:

263668427

result:

wrong answer 1st lines differ - expected: '773406112', found: '263668427'