专栏文章

题解：P14510 夜里亦始终想念着你 miss

ddiqiuyi奶龙
P14510题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min7lhvt
此快照首次捕获于
2025/12/01 21:52
3 个月前
此快照最后确认于
2025/12/01 21:52
3 个月前
查看原文
验题人题解。想这个题的时候思路有点乱，可能导致做法比较冗长。
“段” 指的是 1 的连续段。
有一些观察：操作可逆、在右侧没有 1 时可以将一个长度为偶数的段整体右移一位。
首先操作是可逆的，所以不妨先将尽可能多的 1 挪到最左边形成一个较长的段，然后拿这个段去把 SS 填上。这时候的局面是左侧有一个长段，然后会剩下一些单个的 1。（由于只有长度为偶数的段可以整体移动，如果开头段长为奇数就把最后一个位置当成单个的看待）
设段长为 vv，单个 1 的个数为 cc，位置为 p1∼cp_{1\sim c}，令 pc+1=n+1p_{c+1}=n+1。
把段从左往右滑动，记目前段开头位置为 ss。考虑段的长度是怎么衰减的，发现当且仅当限制要求 ss 这一位为 1 且 s+xs+x 并非单个的 1，而这会导致 v←v−2v\gets v-2。这启示我们考虑段尾从 pip_i 走到 pi+1p_{i+1} 的变化（因为段尾为 pip_i 会导致 vv 不减少）。
设 fi,jf_{i,j} 表示现在有连续的 ii 个位置可以让 v←v−2v\gets v-2，最终 v←v−2jv\gets v-2j 的方案数。有 fi,j=fi−1,j+2fi,j−1f_{i,j}=f_{i-1,j}+2f_{i,j-1}，f0,0=1f_{0,0}=1。设 gjg_j 表示段长最后为 v−2jv-2j 的方案数，则把所有 fpi+1−pi−1f_{p_{i+1}-p_i-1} 卷起来即可。由于滑到末尾后剩下的位置可以乱填，且每个 pip_i 会“保护”一个位置，最后答案为 ∑2i≤vgi2v−2i+c\sum_{2i\le v} g_i2^{v-2i+c}。暴力 dp 复杂度为 O(n3+qn3)O(n^3+qn^3)，但是可以通过 q=0,n≤4000q=0,n\le 4000 的点。
注意到 fi,j=2j(i+j−1j)f_{i,j}=2^j\binom{i+j-1}{j}，把 2j2^j 提出来后相当于是从 (0,0)(0,0) 走到 (i−1,j)(i-1,j) 的方案数。gi=∑{j1,⋯ ,jc}2i∏x=1c(px+1−px−1+jx−1jx)g_i=\sum_{\{j_1,\cdots,j_c\}}2^i\prod_{x=1}^c\binom{p_{x+1}-p_x-1+j_x-1}{j_x}，相当于 2i2^i 乘上 (0,0)(0,0) 到 (∑(px+1−px−1)−1,i)(\sum (p_{x+1}-p_x-1)-1,i) 的方案数。所以 gi=2i(n−c−v+i−1i)g_i=2^i\binom{n-c-v+i-1}{i}，容易 O(n)O(n) 计算。这样就可以 O(qn+n)O(qn+n) 计算答案了。
把式子写出来：ans=∑i=0v22i(n−c−v+i−1i)2v−2i=2v∑i=0v2(n−c−v+i−1i)2−ians=\sum_{i=0}^{\frac{v}2}2^i\binom{n-c-v+i-1}{i}2^{v-2i}=2^v\sum_{i=0}^{\frac{v}2}\binom{n-c-v+i-1}{i}2^{-i}，由于有 2−i2^{-i}，很难快速计算。但是 c,vc,v 都是容易用数据结构维护的，且每次的变化量为 O(1)O(1)，可以使用类似莫队的方式计算。vv 的变化比较好处理，cc 变化时可以利用 (nm)=(n−1m−1)+(n−1m)\binom{n}m=\binom{n-1}{m-1}+\binom{n-1}{m} 处理，可以参考高橋君的处理方法。
时间复杂度为 O(n+qlog⁡n)O(n+q\log n)。
代码和题解有一点出入。
CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
int iv2,n,m,s1,a[500005],nv=-1,cnt,nlen,ans,fac[500005],inv[500005],pw[500005],ip[500005];
string s;
set<pair<int,int>> st;
inline int Pow(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%mod)
		if(y&1)
			res=1ll*res*x%mod;
	return res;
}
int C(int n,int m){
	if(!m) return 1;
	if(n<m||m<0) return 0;
	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void mv(int len,int v){
	while(nlen<len) ans=(ans*2ll-1ll*C(nlen+nv,nv)*ip[nv])%mod,nlen++;
	while(nlen>len) nlen--,ans=1ll*iv2*(ans+1ll*C(nlen+nv,nv)*ip[nv]%mod)%mod;
	while(nv<v) nv++,ans=(ans+1ll*C(len+nv-1,nv)*ip[nv])%mod;
	while(nv>v) ans=(ans-1ll*C(len+nv-1,nv)*ip[nv])%mod,nv--;
}
void solve(){
	if(cnt==s1){
		cout<<pw[cnt]<<'\n';
		return ;
	}
	int p1=s1-cnt+1,len=n+1-p1-cnt,v=p1/2,rv=v*2;
	mv(len,v),ans=(ans+mod)%mod;
	cout<<1ll*ans*pw[cnt+rv]%mod<<'\n';
}
int main(){
//	freopen("miss3.in","r",stdin);
//	freopen("D.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m>>s,iv2=Pow(2,mod-2);
	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
	for(int i=1,len=0;i<=n;i++)
		if(a[i]){
			len++,s1++;
			if(!a[i+1]) cnt+=(len&1),st.insert({i-len+1,i}),len=0;
		}
	fac[0]=pw[0]=ip[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod,pw[i]=2*pw[i-1]%mod,ip[i]=1ll*ip[i-1]*iv2%mod;
	inv[n]=Pow(fac[n],mod-2);
	for(int i=n-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	solve();
	for(int x;m--;){
		cin>>x;
		if(a[x]){
			s1--;
			auto [l,r]=*--st.upper_bound({x,n+1});
			cnt-=((l&1)==(r&1));
			st.erase({l,r});
			if(l<x) cnt+=((l&1)!=(x&1)),st.insert({l,x-1});
			if(x<r) cnt+=((r&1)!=(x&1)),st.insert({x+1,r});
		}
		else{
			s1++;
			auto it=st.upper_bound({x,x});
			int nr=x,nl=x,l=-1,r=-1;
			if(it!=st.end()){
				l=(*it).first,r=(*it).second;
				if(l==x+1) nr=r;
				else l=r=-1;
			}
			if(it!=st.begin()){
				it--;
				int L=(*it).first,R=(*it).second;
				if(R==x-1) nl=L,st.erase({L,R}),cnt-=((L&1)==(R&1));
			}
			if(l!=-1) cnt-=((l&1)==(r&1)),st.erase({l,r});
			st.insert({nl,nr}),cnt+=((nl&1)==(nr&1));
		}
		a[x]^=1;
		solve();
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...