QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#301743 | #3680. 序列染色 | duongnc000 | 100 ✓ | 106ms | 31588kb | C++23 | 3.0kb | 2024-01-10 09:58:42 | 2024-01-10 09:58:42 |
Judging History
answer
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define pb push_back
#define ff first
#define ss second
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 1e6 + 5;
const int mod = 1e9 + 7;
const i64 oo = 1e18;
int binpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod; y >>= 1;
}
return res;
}
string s;
int n, k, dpB[mxN], dpW[mxN], pfx[mxN][3];
int apB[mxN], apW[mxN];
int calc(int l, int r, int idx) {
return pfx[r][idx] - pfx[l - 1][idx];
}
void solve() {
cin >> n >> k >> s; s = " " + s;
for (int i = 1; i <= n; ++i) {
memcpy(pfx[i], pfx[i - 1], sizeof pfx[0]);
if (s[i] == 'X') pfx[i][0]++;
if (s[i] == 'B') pfx[i][1]++;
if (s[i] == 'W') pfx[i][2]++;
}
dpB[0] = 1;
for (int i = 1; i <= n; ++i) {
if (s[i] == 'W') {
dpB[i] = dpB[i - 1];
}
else {
if (s[i] == 'B') dpB[i] = dpB[i - 1];
else dpB[i] = 1ll * dpB[i - 1] * 2 % mod;
if (i >= k and calc(i - k + 1, i, 2) == 0 and s[i - k] != 'B')
dpB[i] = (dpB[i] - (i - k - 1 < 0 ? 1 : dpB[i - k - 1]) + mod) % mod;
}
}
for (int i = k; i <= n; ++i) {
apB[i] = (binpow(2, pfx[i][0]) - dpB[i] + mod) % mod;
}
reverse(s.begin() + 1, s.begin() + n + 1);
dpW[0] = 1;
for (int i = 1; i <= n; ++i) {
memcpy(pfx[i], pfx[i - 1], sizeof pfx[0]);
if (s[i] == 'X') pfx[i][0]++;
if (s[i] == 'B') pfx[i][1]++;
if (s[i] == 'W') pfx[i][2]++;
}
for (int i = 1; i <= n; ++i) {
if (s[i] == 'B') {
dpW[i] = dpW[i - 1];
}
else {
if (s[i] == 'W') dpW[i] = dpW[i - 1];
else dpW[i] = 1ll * dpW[i - 1] * 2 % mod;
if (i >= k and calc(i - k + 1, i, 1) == 0 and s[i - k] != 'W')
dpW[i] = (dpW[i] - (i - k - 1 < 0 ? 1 : dpW[i - k - 1]) + mod) % mod;
}
}
for (int i = k; i <= n; ++i) {
apW[i] = (i - k - 1 < 0 ? 1 : dpW[i - k - 1]) * (calc(i - k + 1, i, 1) == 0) * (s[i - k] != 'W');
}
i64 ans = 0;
for (int i = k; i <= n - k; ++i) {
ans += 1ll * apB[i] * apW[n - i] % mod;
}
cout << ((ans % mod) + mod) % mod << endl;
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
cout << "Check array size pls sir" << endl;
#endif
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 7924kb
input:
1 1000000 X
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 0ms
memory: 9984kb
input:
20 4 XXXXXXXXXXXXXXXXXXXX
output:
108155
result:
ok single line: '108155'
Test #3:
score: 10
Accepted
time: 2ms
memory: 9940kb
input:
2000 200 BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...
output:
590565731
result:
ok single line: '590565731'
Test #4:
score: 10
Accepted
time: 0ms
memory: 9760kb
input:
2000 100 WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...
output:
313979285
result:
ok single line: '313979285'
Test #5:
score: 10
Accepted
time: 2ms
memory: 9800kb
input:
2000 100 XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...
output:
358862528
result:
ok single line: '358862528'
Test #6:
score: 10
Accepted
time: 83ms
memory: 29736kb
input:
765432 5000 WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...
output:
74325182
result:
ok single line: '74325182'
Test #7:
score: 10
Accepted
time: 92ms
memory: 30532kb
input:
876543 5000 WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...
output:
786550221
result:
ok single line: '786550221'
Test #8:
score: 10
Accepted
time: 106ms
memory: 31548kb
input:
1000000 10000 WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...
output:
627927296
result:
ok single line: '627927296'
Test #9:
score: 10
Accepted
time: 105ms
memory: 31588kb
input:
1000000 20000 XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...
output:
412860887
result:
ok single line: '412860887'
Test #10:
score: 10
Accepted
time: 99ms
memory: 31372kb
input:
1000000 50000 WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...
output:
773406112
result:
ok single line: '773406112'