QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#209089 | #3680. 序列染色 | KHIN | 100 ✓ | 31ms | 28096kb | C++17 | 6.0kb | 2023-10-10 09:44:14 | 2023-10-10 09:44:14 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
namespace kh {
constexpr int P(1'000'000'007);
inline namespace src {
template <typename T>
constexpr auto cmin(T& a, T const& b) {
if (b < a) return pair<T&, bool>(a = b, true);
else return pair<T&, bool>(a, false);
}
template <typename T>
constexpr auto cmax(T& a, T const& b) {
if (a < b) return pair<T&, bool>(a = b, true);
else return pair<T&, bool>(a, false);
}
template <typename T>
constexpr auto cminmax(T& a, T& b) {
bool const swp(b < a ? swap(a, b), true : false);
return make_pair(pair<T&, T&>(a, b), swp);
}
template <typename T, class Compare>
constexpr auto cmin(T& a, T const& b, Compare comp) {
if (comp(b, a)) return pair<T&, bool>(a = b, true);
else return pair<T&, bool>(a, false);
}
template <typename T, class Compare>
constexpr auto cmax(T& a, T const& b, Compare comp) {
if (comp(a, b)) return pair<T&, bool>(a = b, true);
else return pair<T&, bool>(a, false);
}
template <typename T, class Compare>
constexpr auto cminmax(T& a, T& b, Compare comp) {
bool const swp(comp(b, a) ? swap(a, b), true : false);
return make_pair(pair<T&, T&>(a, b), swp);
}
template <typename T>
constexpr int sgn(T const x)
{ return (x > 0) - (x < 0); }
template <typename T>
struct frac {
T num, den;
constexpr frac(T const n = 0, T const d = 1)
: num(n / __gcd(n, d)), den(d / __gcd(n, d))
{ assert(den), num *= sgn(den), den *= sgn(den); }
constexpr frac& operator+=(frac const b) { return *this = *this + b; }
constexpr frac& operator-=(frac const b) { return *this = *this - b; }
constexpr frac& operator*=(frac const b) { return *this = *this * b; }
constexpr frac& operator/=(frac const b) { return *this = *this / b; }
constexpr frac& operator++() { return num += den, *this; }
constexpr frac& operator--() { return num -= den, *this; }
constexpr frac operator++(int) { return num += den, *this - 1; }
constexpr frac operator--(int) { return num -= den, *this - 1; }
constexpr frac operator+() const { return frac(+num, den); }
constexpr frac operator-() const { return frac(-num, den); }
friend constexpr frac operator+(frac const a, frac const b)
{ return frac(a.num * b.den + b.num * a.den, a.den * b.den); }
friend constexpr frac operator-(frac const a, frac const b)
{ return frac(a.num * b.den - b.num * a.den, a.den * b.den); }
friend constexpr frac operator*(frac const a, frac const b)
{ return frac(a.num * b.num, a.den * b.den); }
friend constexpr frac operator/(frac const a, frac const b)
{ return frac(a.num * b.den, a.den * b.num); }
friend constexpr bool operator==(frac const a, frac const b)
{ return a.num * b.den == b.num * a.den; }
friend constexpr bool operator!=(frac const a, frac const b)
{ return a.num * b.den != b.num * a.den; }
friend constexpr bool operator<(frac const a, frac const b)
{ return a.num * b.den < b.num * a.den; }
friend constexpr bool operator>(frac const a, frac const b)
{ return a.num * b.den > b.num * a.den; }
friend constexpr bool operator<=(frac const a, frac const b)
{ return a.num * b.den <= b.num * a.den; }
friend constexpr bool operator>=(frac const a, frac const b)
{ return a.num * b.den >= b.num * a.den; }
};
constexpr int pow(int a, int n) {
int r(1);
while (n) {
r = 1l * r * (n & 1 ? a : 1) % P;
a = 1l * a * a % P, n >>= 1;
}
return r;
}
}
constexpr int N(1'000'000);
int n, k;
char s[N + 2];
int cb[N + 1];
int cw[N + 1];
int cx[N + 1];
int f[N + 1];
int g[N + 1];
int t[N + 1];
int ans;
void main() {
cin >> n >> k >> (s + 1);
for (int i(1); i <= n; ++i) {
cb[i] = cb[i - 1] + (s[i] == 'B');
cw[i] = cw[i - 1] + (s[i] == 'W');
cx[i] = cx[i - 1] + (s[i] == 'X');
}
t[0] = f[0] = 1;
for (int i(1), j(0); i <= n; ++i) {
j = max(s[i] == 'W' ? i : j, i - k + 1);
t[i] = s[i] == 'B' ? 0 : f[i - 1];
t[i] = (t[i - 1] + t[i]) % P;
f[i] = (t[i] - (j ? t[j - 1] : 0)) % P;
}
for (int i(n); i >= 0; --i) {
if (i < k) { f[i] = 0; continue; }
if (cw[i] != cw[i - k]) { f[i] = 0; continue; }
if (s[i - k] == 'B') { f[i] = 0; continue; }
f[i] = i - k ? f[i - k - 1] : 1;
}
reverse(s + 1, s + n + 1);
for (int i(1); i <= n; ++i) {
cb[i] = cb[i - 1] + (s[i] == 'B');
cw[i] = cw[i - 1] + (s[i] == 'W');
cx[i] = cx[i - 1] + (s[i] == 'X');
}
t[0] = g[0] = 1;
for (int i(1), j(0); i <= n; ++i) {
j = max(s[i] == 'B' ? i : j, i - k + 1);
t[i] = s[i] == 'W' ? 0 : g[i - 1];
t[i] = (t[i - 1] + t[i]) % P;
g[i] = (t[i] - (j ? t[j - 1] : 0)) % P;
}
for (int i(n); i >= 0; --i) {
if (i < k) { g[i] = 0; continue; }
if (cb[i] != cb[i - k]) { g[i] = 0; continue; }
if (s[i - k] == 'W') { g[i] = 0; continue; }
g[i] = i - k ? g[i - k - 1] : 1;
}
reverse(s + 1, s + n + 1);
for (int i(1); i <= n; ++i) {
cb[i] = cb[i - 1] + (s[i] == 'B');
cw[i] = cw[i - 1] + (s[i] == 'W');
cx[i] = cx[i - 1] + (s[i] == 'X');
}
for (int i(0), s(0); i <= n; ++i) {
s = s * (kh::s[i] == 'X' ? 2 : 1) % P;
s = (s + (i >= k && cw[i] == cw[i - k] ? f[i] : 0)) % P;
if (i + k <= n && cb[i + k] == cb[i])
ans = (ans + 1l * s * g[n - i]) % P;
}
cout << (ans = (ans + P) % P) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t(1);
// cin >> t;
for (int i(1); i <= t; ++i) kh::main();
}
详细
Test #1:
score: 10
Accepted
time: 1ms
memory: 7856kb
input:
1 1000000 X
output:
0
result:
ok single line: '0'
Test #2:
score: 10
Accepted
time: 1ms
memory: 7772kb
input:
20 4 XXXXXXXXXXXXXXXXXXXX
output:
108155
result:
ok single line: '108155'
Test #3:
score: 10
Accepted
time: 1ms
memory: 9856kb
input:
2000 200 BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...
output:
590565731
result:
ok single line: '590565731'
Test #4:
score: 10
Accepted
time: 1ms
memory: 7760kb
input:
2000 100 WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...
output:
313979285
result:
ok single line: '313979285'
Test #5:
score: 10
Accepted
time: 1ms
memory: 7828kb
input:
2000 100 XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...
output:
358862528
result:
ok single line: '358862528'
Test #6:
score: 10
Accepted
time: 15ms
memory: 25060kb
input:
765432 5000 WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...
output:
74325182
result:
ok single line: '74325182'
Test #7:
score: 10
Accepted
time: 26ms
memory: 26120kb
input:
876543 5000 WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...
output:
786550221
result:
ok single line: '786550221'
Test #8:
score: 10
Accepted
time: 19ms
memory: 28020kb
input:
1000000 10000 WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...
output:
627927296
result:
ok single line: '627927296'
Test #9:
score: 10
Accepted
time: 31ms
memory: 28096kb
input:
1000000 20000 XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...
output:
412860887
result:
ok single line: '412860887'
Test #10:
score: 10
Accepted
time: 26ms
memory: 28084kb
input:
1000000 50000 WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...
output:
773406112
result:
ok single line: '773406112'