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)\)
真的只是一点点麻烦
#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());
}
}