CF1450H2 - Multithreading (Hard Version)

Posted on Edited on In

CF1450H2 - Multithreading (Hard Version)

题目大意

给定一个均分成 \(n\) 份( \(n\) 为偶数)的圆，每份上有一个元素为0/1，其中一些元素的值未知，且随机

当存在一个方案，0和0连线，1和1连线，使得每个元素都被恰好连一条线时，称环 \(c\) 合法

定义 \(f(c)\) 为上述连线方案中 不同色连线交叉的最小次数

同时需要支持修改元素，求 \(f(c)\) 的期望


贪心求解指定环

首先考虑一个Naive的贪心，在环上一旦出现相邻两点同色，就将他们连线然后删除

直到最后，就将变成01交替，设此时环长 \(n'\) ，考虑再让相邻的00,11连线

则得到交叉个数为 \(\frac{n'}{4}\)

这个贪心甚至连不带修的情况都做不了

简化求解

考虑上面贪心过程中被抵消的点

容易发现一定是一个奇数位置的点去抵消一个偶数位置的点

并且抵消之后其他位置的奇偶性保持不变

因此猜想最终剩下的黑点数量就是 \(|cnt_{odd}-cnt_{even}|\)

其中 \(cnt_{odd},cnt_{even}\) 表示已经确定的1元素在奇数/偶数位上的个数

也容易证明

根据贪心，显然同奇偶的点无法抵消，因此 \(ans\ge |cnt_{odd}-cnt_{even}|\)

而一旦存在两个不同奇偶的黑点，若他们不相邻

则他们之间一定存在一对相邻白点（否则奇偶性不对），进而不断合并白点使得它们相邻

白点可以对称得到相同值的式子，最终得到答案就是

\(\displaystyle \frac{|cnt_{odd}-cnt_{even}|}{2}\)


答案式子

设已经确定的部分 \(\delta=cnt_{odd}-cnt_{even}\) ，未确定的部分包含 \(x\) 个奇数位置， \(y\) 个偶数位置

则Naive的计算答案式子为

\(\displaystyle Sum=\sum_{i=0}^x \sum_{j=0}^y \frac{1}{2}\cdot [2|i-j+\delta] \cdot |\delta+i-j|\binom{x}{i}\binom{y}{j}\)

NTT

补上方案数 \(2^{x+y-1}\) （因为只有一半的方案奇偶性相同），用 \(y-j\) 代换 \(j\)

\(\displaystyle E=\frac{1}{2^{x+y}}\sum_{i=0}^x \sum_{j=0}^y \cdot [2|i-y+j+\delta] \cdot |\delta+i-y+j|\binom{x}{i}\binom{y}{j}\)

转换为 \(\displaystyle i+j\leftarrow \binom{x}{i}\binom{y}{j}\) 的形式后，带入组合意义合并 \(i,j\)

\(\displaystyle E=\frac{1}{2^{x+y}}\sum_{i=0}^{x+y} \cdot [2|\delta-y+i] \cdot |\delta-y+i|\binom{x+y}{i}\)

不妨设 \(\delta'=\delta-y\)

\(\displaystyle E=\frac{1}{2^{x+y}}\sum_{i=0}^{x+y} \cdot [\delta'\equiv i\pmod 2] \cdot |\delta'+i|\binom{x+y}{i}\)

根据 \(\delta'+i\) 的正负性容易确定一个范围，范围两边都是计算都转化为

\(\displaystyle S(n,m)=\sum _{i=0}^m [2\not |i]\cdot i\cdot \binom{n}{i}\)

\(\displaystyle S(n,m)=\sum _{i=0}^m [2\not |i]\cdot n\cdot \frac{(n-1)!}{(n-i)!(i-1)!}\)

\(\displaystyle S(n,m)=n\sum _{i=0}^{m-1} [2 |i]\cdot \binom{n-1}{i}\)

形如 \(\displaystyle m|2, S'(n,m)=\sum _{i=0}^m [2|i]\cdot \binom{n}{i}\) ，可以转化为

\(\displaystyle S'(n,m)=\sum _{i=0}^m [2|i](\binom{n-1}{i}+\binom{n-1}{i-1})\)

\(\displaystyle S'(n,m)=\sum _{i=0}^m \binom{n-1}{i}\)

组合数关于 \(m\) 一维的前缀和是一个经典的步移问题

\(S(n,m-1)=S(n,m)-C(n,m)\)

\(S(n,m+1)=S(n,m)+C(n,m+1)\)

\(S(n+1,m)=\displaystyle \sum_{i=0}^m C(n+1,m)=\sum_{i=0}^mC(n,i)+\sum_{i=0}^{m-1}C(n,i-1)=2S(n,m)-C(n,m)\)

\(\displaystyle S(n-1,m)=\frac{S(n,m)+C(n-1,m)}{2}\)

封装一下计算即可，复杂度为 \(O(n)\)

真的只是一点点麻烦

QQ图片20210506191744.jpg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
char IO;
int rd(){
	int s=0;
	while(!isdigit(IO=getchar()));
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return s;
}

const int N=2e5+10,P=998244353;

int n,m;
int I[N],J[N];
int P1[N],P2[N];
ll qpow(ll x,ll k=P-2){
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}

char s[N];
int d,x,y;

int Pow2(int x){ return x<0?P2[-x]:P1[x]; }
int C(int n,int m){ return n<0||m<0||n<m?0:1ll*J[n]*I[m]%P*I[n-m]%P; }

int p1,p2,cur=1;
// 组合数关于m的前缀和，步移计算
int SC(int n,int m) {
	if(n<0||m<0) return 0;
	if(m==0) return 1;
	if(m>=n) return Pow2(n);
	if(m==n-1) return Pow2(n)-1;

	/* Brute Force
	int sum=0;
	rep(i,0,m) sum=(sum+C(n,i))%P; 
	return sum;
	*/

	/* assertions blows
	static int fl=1; 
	assert(fl || abs(p1-n)+abs(p2-m)<=10);
	fl=0;
	*/

	while(p2>m) cur=(cur-C(p1,p2--))%P;
	while(p2<m) cur=(cur+C(p1,++p2))%P;
	while(p1<n) cur=(cur*2ll-C(p1++,p2))%P;
	while(p1>n) cur=1ll*(cur+C(--p1,p2))*(P+1)/2%P;
	return cur;
}

// T 指前面的S'
int T(int n,int m,int k){ return k==1?(SC(n,m)-T(n,m,0))%P:(n==0?m>=0:SC(n-1,m-(m&1))); }
int T(int n,int l,int r,int k){ 
	
	/*Brute Force
	int sum=0;
	rep(i,l,r) if((i&1)==k) sum=(sum+C(n,i))%P;
	return sum;
	*/

	return l>r?0:(T(n,r,k)-T(n,l-1,k))%P; 
}

int S(int n,int m){ return 1ll*n*T(n-1,m-1,0)%P; }
int S(int n,int l,int r,int k=1){

	/*Brute Force
	int sum=0;
	rep(i,l,r) if((i&1)==k) sum=(sum+1ll*i*C(n,i))%P;
	return sum;
	*/

	if(l>r) return 0;
	if(k==0) return (1ll*n*(SC(n-1,r-1)-SC(n-1,l-2))-S(n,l,r))%P;
	return (S(n,r)-S(n,l-1))%P;
}

int Que(){
	int D=d-y,n=x+y,ans=0;
	/* Brute Force
	rep(i,0,n) if((i&1)==(D&1))  {
		ans=(ans+1ll*abs(D+i)*C(n,i))%P;
	}
	*/
	if(D<0) {
		int t=-D-1;
		ans=(ans-1ll*D*T(n,t,D&1))%P;
		ans=(ans-S(n,0,t,D&1))%P;
	}
	if(D+n>=0) {
		ans=(ans+1ll*D*T(n,max(0,-D),n,D&1))%P;
		ans=(ans+S(n,max(0,-D),n,D&1))%P;
	}
	ans=1ll*(ans+P)*Pow2(-n)%P;
	return ans;
}

int main(){
	rep(i,*P1=1,N-1) P1[i]=P1[i-1]*2,Mod1(P1[i]);
	rep(i,*P2=1,N-1) P2[i]=((P2[i-1]&1)?P2[i-1]+P:P2[i-1])/2;
	rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P;
	n=rd(),m=rd(),scanf("%s",s+1);
	rep(i,1,n) {
		if(s[i]=='b') i&1?d++:d--;
		if(s[i]=='?') i&1?x++:y++;
	}
	printf("%d\n",Que());
	while(m--) {
		int i=rd(),c=getchar();
		if(s[i]=='b') i&1?d--:d++;
		if(s[i]=='?') i&1?x--:y--;
		s[i]=c;
		if(s[i]=='b') i&1?d++:d--;
		if(s[i]=='?') i&1?x++:y++;
		printf("%d\n",Que());
	}
}