Problem solution CF1450H1 [Multithreading (Easy Version)]

First, assume that there is no \ (? \).

First of all, konjaku gives an easy to think of greed:

Each time, select two adjacent positions with the same color, and then pair them

If the pairing fails, the current state must be \ (wbwbwbwbwbwbwbwbwb... \), and there must be \ (\ frac{cnt}{2} \) intersections\ (CNT \) is the number of \ (b \).

So the answer to the whole question is \ (| \ frac{cnta - cntb}{2 | \), \ (cnta \) is the number of times \ (b \) appears in the position with odd subscript, and \ (cntb \) is the number of times \ (b \) appears in the position with even subscript.

How to prove that this is the smallest?

First, you can make the intersecting line segments of the same color of the whole graph become disjoint, and the answer is strictly not increased.

Consider mathematical induction:

  • An empty picture, or a picture with only white dots, answer \ (= 0 \ge |\frac{cnta - cntb}{2} \)

  • For a non empty graph, first find two connected black spots, and they are adjacent in the black spots (they must be found):

    • One of the two points is at the odd subscript number and the other is at the even subscript number: then one side of the two points is a white point, which can be matched by itself, and the answer on the other side \ (\ ge |\frac{(cnta - 1) - (cntb - 1)}{2}| = |\frac{cnta - cntb}{2}| \). So it was established.

    • Both points are at the odd subscript or even subscript: then one side of both points is white, but there will be one more point, then the white point and its corresponding point will produce an intersection with the connected edge found now. Answer (you may wish to select two points with odd subscripts) \ (\ Ge 1 + | \ frac {(CNTA - 2) - cntb} | = 1 + | \ frac {CNTA - cntb} {2} - 1| \ Ge | \ frac {CNTA - cntb} {2} | \)

The certificate is completed.

The number of odd subscripts of \ (b \) minus even subscripts is \ (cnta \), \ (? \) in odd subscripts is \ (cntb \), \ (? \) in even subscripts is \ (cntc \).

\[ans = \frac{1}{2^{cntb + cntc - 1}} \sum\limits_{i = 0}^{cntb} \sum\limits_{j = 0}^{cntc} |cnta + i - j| C_{cntb}^{i} C_{cntc}^{j} \]

\[= \frac{1}{2^{cntb + cntc - 1}} \sum\limits_{i = 0}^{cntb} \sum\limits_{j = 0}^{cntc} |cnta + i + (cntc - j)| C_{cntb}^{i} C_{cntc}^{j} \]

Then this thing can be convoluted.

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++) 
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long 
#define db long double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 6e5 + 7;
const int mod = 998244353;
const int G = 3;
const int iG = (mod + 1) / G;
int qpow(int x, int y) {
	int res = 1;
	for(; y; x = 1ll * x * x % mod, y >>= 1) if(y & 1) res = 1ll * res * x % mod;
	return res;
}
int ny(int x) { return qpow(x, mod - 2); }
int pp[N];
void NTT(int *f, int len, int flag) {
	L(i, 0, len - 1) if(pp[i] < i) swap(f[pp[i]], f[i]);
	for(int i = 2; i <= len; i <<= 1) 
		for(int j = 0, l = (i >> 1), ch = qpow(flag == 1 ? G : iG, (mod - 1) / i); j < len; j += i) 
			for(int k = j, now = 1; k < j + l; k ++) {
				int pa = f[k], pb = 1ll * f[k + l] * now % mod;
				f[k] = (pa + pb) % mod, f[k + l] = (pa - pb + mod) % mod, now = 1ll * now * ch % mod;
			}
	if(flag == -1) {
		int nylen = ny(len);
		L(i, 0, len - 1) f[i] = 1ll * f[i] * nylen % mod;
	}
}
void George1123(int *f, int *g, int *ans, int lena, int lenb) { // Tornado king
	int lim; for(lim = 1; lim <= lena + lenb; lim <<= 1);
	L(i, 0, lim - 1) pp[i] = ((pp[i >> 1] >> 1) | ((i & 1) * (lim >> 1)));
	NTT(f, lim, 1), NTT(g, lim, 1);
	L(i, 0, lim - 1) ans[i] = 1ll * f[i] * g[i] % mod;
	NTT(ans, lim, -1);
}
int n, m, cnta, cntb, cntc, jc[N], njc[N], ans, f[N], g[N], h[N];
int C(int x, int y) { return 1ll * jc[x] * njc[y] % mod * njc[x - y] % mod; }
char s[N];
int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	jc[0] = njc[0] = 1;
	L(i, 1, n) jc[i] = 1ll * jc[i - 1] * i % mod, njc[i] = ny(jc[i]);
	L(i, 1, n) {
		if(s[i] == 'b') {
			if(i % 2) cnta ++;
			else cnta --;
		}
		else if(s[i] == '?') {
			if(i % 2) cntb ++;
			else cntc ++;
		}
	}
	L(i, 0, cntb) f[i] = C(cntb, i);
	L(i, 0, cntc) g[i] = C(cntc, i);
	George1123(f, g, h, cntb, cntc);
	L(i, 0, cntb + cntc) if((cnta + i - cntc) % 2 == 0) (ans += 1ll * abs(cnta + i - cntc) / 2 * h[i] % mod) %= mod;
	ans = 1ll * ans * qpow(ny(2), cntb + cntc - 1) % mod;
	printf("%d\n", ans);
	return 0;
}

Now you can pass \ (H1 \), but give a better way to write and lay the foundation for \ (H2 \):

Consider how to optimize the convolution formula \ (f_t = \ sum \ limits {I = 0} ^ {a} c_ {a} ^ I \ sum \ limits {J = 0} ^ {B} C {B} ^ {J} [i + J = t] \)

Observe the law and find \ (f_t = C_{a+b}^t \), how to prove it?

Consider its combination significance\ (C_{a+b}^t \) is equivalent to taking out \ (t \) from \ (a + b \) balls, so we can enumerate the number taken out from the previous \ (a \) and the number taken out from the previous \ (b \), that is, \ (\ sum \ limits {I = 0} ^ {a} C {a} ^ I \ sum \ limits {J = 0} ^ {b} C {b} ^ {J} [i + J = t] \).

So the answer is \ (\ frac {1} {2 ^ {cntb + CNTC}} \ sum \ limits {I = 0, I \ equiv CNTA - CNTC {cntb + CNTC} ^ {I} \)

This formula looks uncomfortable, let \ (cnt = cntb + cntc, t = cnta - cntc \)

\(ans = \frac{1}{2^{cnt}} \sum\limits_{i = 0, i \equiv t \pmod 2}^{cnt} |t + i| C_{cnt}^{i}\)

So we get more concise code:

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = j, i##E = k; i <= i##E; i++) 
#define R(i, j, k) for(int i = j, i##E = k; i >= i##E; i--)
#define ll long long
#define ull unsigned long long 
#define db long double
#define pii pair<int, int>
#define mkp make_pair
using namespace std;
const int N = 2e5 + 7;
const int mod = 998244353;
int qpow(int x, int y) {
	int res = 1;
	for(; y; x = 1ll * x * x % mod, y >>= 1) if(y & 1) res = 1ll * res * x % mod;
	return res;
}
int ny(int x) { return qpow(x, mod - 2); }
int n, m, t, cnt, jc[N], njc[N], ans;
int C(int x, int y) { return 1ll * jc[x] * njc[y] % mod * njc[x - y] % mod; }
char s[N];
int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	jc[0] = njc[0] = 1;
	L(i, 1, n) jc[i] = 1ll * jc[i - 1] * i % mod, njc[i] = ny(jc[i]);
	L(i, 1, n) {
		if(s[i] == 'b') {
			if(i % 2) t ++;
			else t --;
		}
		else if(s[i] == '?') {
			cnt ++;
			if(i % 2 == 0) t --;
		}
	}
	L(i, 0, cnt) if((t + i) % 2 == 0) (ans += 1ll * abs(t + i) * C(cnt, i) % mod) %= mod;
	ans = 1ll * ans * qpow(ny(2), cnt) % mod;
	printf("%d\n", ans);
	return 0;
}

Posted by MrKaraokeSteve on Sun, 01 May 2022 20:13:58 +0300