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

· · 题解

验题人题解。想这个题的时候思路有点乱，可能导致做法比较冗长。

“段” 指的是 1 的连续段。

有一些观察：操作可逆、在右侧没有 1 时可以将一个长度为偶数的段整体右移一位。

首先操作是可逆的，所以不妨先将尽可能多的 1 挪到最左边形成一个较长的段，然后拿这个段去把 S 填上。这时候的局面是左侧有一个长段，然后会剩下一些单个的 1。（由于只有长度为偶数的段可以整体移动，如果开头段长为奇数就把最后一个位置当成单个的看待）

设段长为 v，单个 1 的个数为 c，位置为 p_{1\sim c}，令 p_{c+1}=n+1。

把段从左往右滑动，记目前段开头位置为 s。考虑段的长度是怎么衰减的，发现当且仅当限制要求 s 这一位为 1 且 s+x 并非单个的 1，而这会导致 v\gets v-2。这启示我们考虑段尾从 p_i 走到 p_{i+1} 的变化（因为段尾为 p_i 会导致 v 不减少）。

设 f_{i,j} 表示现在有连续的 i 个位置可以让 v\gets v-2，最终 v\gets v-2j 的方案数。有 f_{i,j}=f_{i-1,j}+2f_{i,j-1}，f_{0,0}=1。设 g_j 表示段长最后为 v-2j 的方案数，则把所有 f_{p_{i+1}-p_i-1} 卷起来即可。由于滑到末尾后剩下的位置可以乱填，且每个 p_i 会“保护”一个位置，最后答案为 \sum_{2i\le v} g_i2^{v-2i+c}。暴力 dp 复杂度为 O(n^3+qn^3)，但是可以通过 q=0,n\le 4000 的点。

注意到 f_{i,j}=2^j\binom{i+j-1}{j}，把 2^j 提出来后相当于是从 (0,0) 走到 (i-1,j) 的方案数。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}，相当于 2^i 乘上 (0,0) 到 (\sum (p_{x+1}-p_x-1)-1,i) 的方案数。所以 g_i=2^i\binom{n-c-v+i-1}{i}，容易 O(n) 计算。这样就可以 O(qn+n) 计算答案了。

把式子写出来：ans=\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^{-i}，很难快速计算。但是 c,v 都是容易用数据结构维护的，且每次的变化量为 O(1)，可以使用类似莫队的方式计算。v 的变化比较好处理，c 变化时可以利用 \binom{n}m=\binom{n-1}{m-1}+\binom{n-1}{m} 处理，可以参考高橋君的处理方法。

时间复杂度为 O(n+q\log n)。

代码和题解有一点出入。

#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;
}