QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#301736#3680. 序列染色duongnc00010 34ms31608kbC++233.0kb2024-01-10 09:30:142024-01-10 09:30:14

Judging History

This is the latest submission verdict.

  • [2024-01-10 09:30:14]
  • Judged
  • Verdict: 10
  • Time: 34ms
  • Memory: 31608kb
  • [2024-01-10 09:30:14]
  • Submitted

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] - dpB[i - k] + mod) % mod;
		}
		// cout << i << " " << dpB[i] << endl;
	}
	for (int i = k; i <= n; ++i) {
		apB[i] = (i - k - 1 < 0 ? 1 : dpB[i - k - 1]) * (calc(i - k + 1, i, 'W') == 0) * (s[i - k] != 'B');
	}
	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] - dpW[i - k] + 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, 'B') == 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 << 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: 3584kb

input:

1 1000000
X


output:

0

result:

ok single line: '0'

Test #2:

score: 0
Wrong Answer
time: 1ms
memory: 3520kb

input:

20 4
XXXXXXXXXXXXXXXXXXXX


output:

10008

result:

wrong answer 1st lines differ - expected: '108155', found: '10008'

Test #3:

score: 0
Wrong Answer
time: 1ms
memory: 3596kb

input:

2000 200
BBBXBBBXXXBBBWXXXXXXBBXBBBXBXXXBXBXBXBXXXBXBBXBBXXXXXBBXBBBBXXBBXBBXXBBBXBXBBBBXBBBXXBBBXXBXXXXXXXBBXBXBBBBBBXXBBXBXXBXXBXXBBXBBBXXXBXBXBXBBXBXBBXBBXXXXBXXBXBXXXXBXXBXBBXBBXBBXBXBBXBXBBBXBXBXBXBBXXXBXBXXXXBBXXXXXBBXBXBBXXBBBXXXXXXBBXBXBXBBXBXXBBXBBBXBBBXXXXBXXBXXBBBXBXXBXXXBXBXXXXBBXBXBXBXB...

output:

0

result:

wrong answer 1st lines differ - expected: '590565731', found: '0'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 3536kb

input:

2000 100
WWWXXWXWXWXXWWXXBWXWXXWXXWXWWXXWWXWXXXXXWXWXWWWWXWWXWXWWXWWXWXXXXXWXXWWWXXXXXWWXWXWWXWXWXXWXXWWXXWWWXXWWWWWXXXWWXXXXXWWWWXWWXWWWXWWXWWWXWXWXWWWWXWXWWXWWXXXXXWXWWWXXXWXXXXXWXXWWXWXXWXWXWWWWWWXXWXWXWWWXXWXXXXXXWWWXXXXWWWXWWBBXBBBBXXXBXBXBXBBBXXBXBXXXBBBBXXXXXBBXBBBXBXXBBBBBBBXBBXBBXBBXXXXXXBB...

output:

0

result:

wrong answer 1st lines differ - expected: '313979285', found: '0'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3532kb

input:

2000 100
XWXXXWWWXWWWXWXXWWWWWWXXXXXWXXWXWWXWWWXXWWWWXWXXXWWWXXWXWXWXWWXXXXWXXWXWWWXWXWWXXWXXWXWXXWXXXXXXWXXWXWXXXWXXXWXXWWBXXXXBXXXBBBXBBXXBBBXBXXBBXBXBBXBBBBXBBXBBXXXXBBBBBBBXXBBXXXBXBBXBBBXBBBXBXBXXBXBXBBBXBXXBBXBBXBXXXBBBBBXXXBXBXBBXXBBXXXXXBBXXBBXBBXBXBBBBBXBBBBXBBXBBBBBBBBBBBXXXXXBXXXBBXBBXBBX...

output:

0

result:

wrong answer 1st lines differ - expected: '358862528', found: '0'

Test #6:

score: 0
Wrong Answer
time: 24ms
memory: 24952kb

input:

765432 5000
WXWWWXWWWWXXWXXXWWXWXWWXXWXWWXWXWWXXXXXXWWWWWXWWWWXXWXXXWWWWXWXWWXXWXXXWXWXWWWWWXWWWWWWXXWWWXWWWXXWXXXWXXXXXXWXXXWWWWWWXWXWXXWXWWWWWXWWXXXWXXWWXWWXXXWWXWXXWXWXWXXXWWXXXWXXXXWXWWXWXWWWWXWXXXXXWXXWWWWWXXWXXXXXWWWWWWXXWWXWWXWXXXWXWWWXXXWXXWWXWXWXWXWXXWWWXXXWWWXXWXWWXWWWXWXXXXXWXWXWXWWXXWWWX...

output:

0

result:

wrong answer 1st lines differ - expected: '74325182', found: '0'

Test #7:

score: 0
Wrong Answer
time: 34ms
memory: 28096kb

input:

876543 5000
WWWWXXWXWXWXXWWXXWWWXWXWWXXXWWXXWXXXWXXXXWWXWXWXXXWXWWXXXXWWWWXXXXXXWWXXWXXWXWXWWXXXWXWWWWXWWWXWWWWWWWWXWXWWXXWWWWWXXXWWWXXWWWWWXXWXWXXWWWXWXXXWXWWWWWWWXXWWWXWXXXXXWWWXXWXWWXXXWXWWWWWXWWXWWXXWXWWWXWWWWWWWXXXXWWXXWXWXXXWWXWXXWXWWXXXXWWXXXWXWWXXXXXWWXWXXXWWWXXXWXWWXWWWXXXXWWWXWWWWXXXWWWWWW...

output:

0

result:

wrong answer 1st lines differ - expected: '786550221', found: '0'

Test #8:

score: 0
Wrong Answer
time: 27ms
memory: 31608kb

input:

1000000 10000
WWWXWWWWWXWXWWWXWWXWXWXWXXWWXWWXWXWXWXWWXWXXWWXXXWXWXXWWWWWWXXXXWWWXXXWWWWWXWWWWXXWWXXWWXWWWXWXWXWWWWXXXXWXXXWWXWWWWWXXWXXWXXWXWXXXWXXXXXXXXWXXXWWXWWWWWWWXWXWWWWWWXWWWXWXXXXWWWWWXWWXWWWWWXWXWWXXWWWWXWWXXXXWWXWXWWWXWWWWWXWWWWWWXXXWXWWWWWXWXWXXWXWXXWWXWWWXWWWXWXWWXWXXXXWXXXXXWXXWXWXXWXWX...

output:

0

result:

wrong answer 1st lines differ - expected: '627927296', found: '0'

Test #9:

score: 0
Wrong Answer
time: 31ms
memory: 31464kb

input:

1000000 20000
XWXWWWWWXWWWXXWWXWWXWXWXWWXWWXXXXWWXXWWXXWWWWXWXWXWWWXWXXXWWXXXWXXWWXXXWXWWWWWWWWXXWXWXXWWWXWXWXXWWWXWXXWXXWWWWXWXXXXWXWWWXWXWWWXXWXXXWXXXWXWXWXXWWWWXXXXXXWXWWWWXWXWXXXXWXWXWWWWXWWWWWWWWWWWXWXXXWXWXWXXXWXWWWWWWXXXXWXWWWWWWXXXXWXXXXXWXWWWWWWWXXXWWWWWXWWXWXXWWXXWWWXWXXXWXWWXXWWXXWXXXWWWW...

output:

0

result:

wrong answer 1st lines differ - expected: '412860887', found: '0'

Test #10:

score: 0
Wrong Answer
time: 25ms
memory: 31216kb

input:

1000000 50000
WXXXXXXXWWWWWXWXWXXXWXXXWWXWWWWXXXWWBWWXWWXXXXXXXXXWWWXXXWXXWXWWWWXWXWWWXWWWXXWWXXWXWWWXXXXWWWWWXWXWWXXWXXWWWXXWWWWWXWWXWWWWWWWXWWXWXXWWWXWXWWWXWXWWWXXXXWXWWWWWWXXWXXWWWXWXWXWXWXXXWXWXXWWWXWWWXWWWWXWWXWWWWXWXXWWXWWWXWXWWWXXXXWXWWWXWXXXWWXXWWXXWXXWXWXWXXWWWXWWWXXXWWXWXXWXWXXWWXWXXWXWWXW...

output:

0

result:

wrong answer 1st lines differ - expected: '773406112', found: '0'