CF2077C Binary Subsequence Value Sum题解

· · 题解

源神场给的组合数学基础式子练习题。 ### 题意 对于一个 $01$ 串 $v$，设 $\operatorname{zero}(v,l,r)$ 表示 $v$ 中区间 $[l,r]$ 中 $0$ 的数量，设 $F(v,l,r)=r-l+1-2\operatorname{zero}(v,l,r)$，特别的，当 $l>r$ 时，$F(v,l,r)=0$。 定义 $01$ 串 $v$ 的权值为： $$\max_{i=1}^{|v|}F(v,1,i-1)\times F(v,i,|v|)$$ 现在给出一个长度为 $n$ 的 $01$ 串 $s$，$q$ 次修改，每次反转一位 $01$，每次修改后回答 $s$ 所有子序列的权值和，答案对 $998244353$ 取模。 $n,q\le2\times10^5$。 ### 做法 需要用到的两个式子：$\sum_{i=0}^nC_{n}^ii=n2^{n-1}$,$\sum_{i=0}^nC_n^ii^2=n(n+1)2^{n-2}$。 （如果你并不理解上述两个式子，可以看文章最后的证明部分） 首先我们发现 $F(v,l,r)$ 实际就是区间 $[l,r]$ 内 $1$ 的个数减 $0$ 的个数，于是 $F(v,1,i-1)+F(v,i,|v|)=F(v,1,|v|)$。 设 $F(v,1,|v|)=\delta_v$，我们知道两个数的和一定时两者差越小乘积越大，所以 $v$ 的权值等于 $\lfloor\frac{\delta_v}{2}\rfloor\lceil\frac{\delta_v}{2}\rceil$。 这个一看就比较难受，按 $\delta_v$ 的奇偶性讨论一下： - 当 $\delta_v$ 为奇数时，上式等于 $\frac{(\delta_v-1)(\delta_v+1)}{4}

所以上述式子等于 \frac{\delta_v^2-[\delta_v\equiv1\pmod2]}{4}。

发现 \delta_v 为奇数当且仅当 v 的长度为奇数，所以我们可以算出需减一的总数量为 2^{n-1}，即长度为奇数的子序列数量，于是我们只需解决每个子序列的 \delta_v 平方和。

设 cnt_{0/1} 表示 v 中 0/1 的数量，那么 \delta_v^2=(cnt_0-cnt_1)^2=cnt_0^2+cnt_1^2-2cnt_0cnt_1。

设 tot_{0/1} 表示 s 中 0/1 的个数。

我们分别解决 cnt_{0/1}^2 之和以及 cnt_0cnt_1 之和：

cnt_{0/1}^2 之和

以 cnt_0^2 为例，cnt_1^2 同理。

显然答案为 2^{tot_1}\sum_{i=0}^{tot_0}C_{tot_0}^ii^2，即我们枚举 cnt_0 的大小，然后算有这么多 0 的子序列个数乘 cnt_0^2。

根据开头提到的 \sum_{i=0}^nC_n^ii^2=n(n+1)2^{n-2} 可以得到上式等于 2^{tot_1}tot_{0}(tot_0+1)2^{tot_0-2}=tot_{0}(tot_0+1)2^{n-2}。

那么同理，cnt_1^2 之和等于 tot_1(tot_1+1)2^{n-2}。

cnt_0cnt_1 之和

显然答案为 \sum_{i=0}^{tot_0}\sum_{j=0}^{tot_1}C_{tot_0}^iC_{tot_1}^jij=\sum_{i=0}^{tot_0}C_{tot_0}^ii\times\sum_{j=0}^{tot_1}C_{tot_1}^jj。

用开头提到的 \sum_{i=0}^nC_n^ii=n2^{n-1} 可以得到上式等于 tot_0tot_12^{n-2}。

那么答案就等于：

\frac{(\sum cnt_0^2)+(\sum cnt1^2)-2(\sum cnt_0cnt_1)-2^{n-1}}{4}

等于（为了简洁，以下以 x,y 分别代表 cnt_0,cnt_1）：

\frac{x(x+1)2^{n-2}+y(y+1)2^{n-2}-xy2^{n-1}-2^{n-1}}{4}

在修改过程中维护 tot_0 和 tot_1，然后直接输出上式即可，时间复杂度 O(\sum n+q)。

代码

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
#define sh short
#define csh const short
#define ush unsigned short
#define cush const unsigned short
using namespace std;
int read()
{
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x;
}
void print(cint x)
{
    if(x<10)
    {
        putchar(x+'0');
        return;
    }
    print(x/10);
    putchar(x%10+'0');
}
void princh(cint x,const char ch)
{
    print(x);
    putchar(ch);
}
cint mod=998244353,iv2=499122177,iv4=1ll*iv2*iv2%mod;
int n,q,c[2];
bool a[200001];
int pw[400001];
void init()
{
    pw[0]=1;
    for(int i=1;i<=4e5;++i)
    {
        pw[i]=(pw[i-1]<<1)%mod;
    }
}
int PW(cint x)
{
    if(x==-1)return iv2;
    if(x==-2)return iv4;
    return pw[x];
}
int calc(cint x,cint y)
{
    return 1ll*iv4*(1ll*x*(x+1)%mod*PW(x+y-2)%mod+1ll*y*(y+1)%mod*PW(x+y-2)%mod+(mod-1ll*x*y%mod*PW(x+y-1)%mod)%mod+(mod-PW(x+y-1)))%mod;
}
void query()
{
    cint x=read();
    --c[a[x]];
    a[x]^=1;
    ++c[a[x]];
    princh(calc(c[0],c[1]),'\n');
}
void solve()
{
    n=read();
    q=read();
    char ch=getchar();
    while(ch!='0'&&ch!='1')ch=getchar();
    c[0]=c[1]=0;
    for(int i=1;i<=n;++i)
    {
        a[i]=ch-'0';
        ++c[a[i]];
        ch=getchar();
    }
    while(q--)query();
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    init();
    int T=read();
    while(T--)solve();
    return 0;
}

证明

证明 \sum_{i=0}^nC_n^ii=n2^{n-1}

#### 证明 $\sum_{i=0}^nC_n^ii^2=n(n+1)2^{n-2}

考虑 i^2=i+i(i-1)=i+2\times\frac{i(i-1)}{2}=C_i^1+2C_i^2，则原式等于 \sum_{i=0}^nC_n^iC_i^1+2C_n^iC_i^2，等于 n2^{n-1}+2\sum_{i=0}^nC_n^iC_i^2，则我们只需解决 \sum_{i=0}^nC_n^iC_i^2。

考虑组合意义，即从 n 个元素里选出若干个，再从若干个元素里选出两个的方案数。那我们先选出这两个，有 \frac{n(n-1)}{2} 种方案，然后再从剩下的元素中选出若干个，有 2^{n-2} 种方案，所以有 n(n-1)2^{n-3} 种方案。

则原式等于 n2^{n-1}+2\times n(n-1)2^{n-3}=2n\times 2^{n-2}+n(n-1)\times2^{n-2}=n(n+1)2^{n-2}。