QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882546 | #3680. 序列染色 | _rey | 20 | 89ms | 16192kb | C++17 | 1.9kb | 2025-02-05 09:16:03 | 2025-02-05 09:16:05 |
Judging History
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'