QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #882538 | #3680. 序列染色 | _rey | 0 | 95ms | 16108kb | C++17 | 1.8kb | 2025-02-05 09:11:09 | 2025-02-05 09:11:10 |
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;
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 - 1 >= 0) {
if (s[i - k - 1] == 'X') ++cnt;
sum = sum*mint(2) + dpB[i - k - 1];
}
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 - 1) {
if (s[i + k + 1] == 'X') ++cnt;
sum = sum*mint(2) + dpW[i + k + 1];
}
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: 0
Runtime Error
input:
1 1000000 X
output:
result:
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
20 4 XXXXXXXXXXXXXXXXXXXX
output:
50323
result:
wrong answer 1st lines differ - expected: '108155', found: '50323'
Test #3:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
2000 200 BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...
output:
566977440
result:
wrong answer 1st lines differ - expected: '590565731', found: '566977440'
Test #4:
score: 0
Wrong Answer
time: 1ms
memory: 3712kb
input:
2000 100 WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...
output:
327415437
result:
wrong answer 1st lines differ - expected: '313979285', found: '327415437'
Test #5:
score: 0
Wrong Answer
time: 1ms
memory: 3584kb
input:
2000 100 XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...
output:
510718248
result:
wrong answer 1st lines differ - expected: '358862528', found: '510718248'
Test #6:
score: 0
Wrong Answer
time: 73ms
memory: 13204kb
input:
765432 5000 WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...
output:
217578140
result:
wrong answer 1st lines differ - expected: '74325182', found: '217578140'
Test #7:
score: 0
Wrong Answer
time: 84ms
memory: 14512kb
input:
876543 5000 WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...
output:
497861355
result:
wrong answer 1st lines differ - expected: '786550221', found: '497861355'
Test #8:
score: 0
Wrong Answer
time: 94ms
memory: 16100kb
input:
1000000 10000 WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...
output:
884609921
result:
wrong answer 1st lines differ - expected: '627927296', found: '884609921'
Test #9:
score: 0
Wrong Answer
time: 89ms
memory: 16108kb
input:
1000000 20000 XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...
output:
91606828
result:
wrong answer 1st lines differ - expected: '412860887', found: '91606828'
Test #10:
score: 0
Wrong Answer
time: 95ms
memory: 16100kb
input:
1000000 50000 WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...
output:
956571999
result:
wrong answer 1st lines differ - expected: '773406112', found: '956571999'