QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301743#3680. 序列染色duongnc000100 ✓106ms31588kbC++233.0kb2024-01-10 09:58:422024-01-10 09:58:42

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 09:58:42]
  • 评测
  • 测评结果:100
  • 用时:106ms
  • 内存:31588kb
  • [2024-01-10 09:58:42]
  • 提交

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'