P5982 题解

· · 题解

P5982

感觉思路挺自然的，但是本人太菜调试了数年。

思路

首先，正难则反，用总方案数减去三个都不满足的方案数。

对于一个位置，填 1 和填 0 所造成的贡献完全相反。假如填 1 造成的贡献是 (1,1,0)，填 0 则贡献 (0,0,1)，其他情况类似。

对于每个位置按照造成的贡献进行分类。由于每个位置有两种贡献方式，所以我们钦定对 \rm{d}(S,s_1) 贡献为 1 的贡献方式为分类的依据。这样就会分出 (1,1,1),(1,1,0),(1,0,1),(1,0,0) 四类。同时设 (x,y,z) 这一类的个数为 G_{xyz}，比如 (1,1,0) 的个数为 G_{110}。

考虑我们要计数的东西是什么。也就是在 G_{xyz} 个位置中挑选 F_{xyz} 个造成 (x,y,z) 的贡献，余下 G_{xyz}-F_{xyz} 个位置造成 (x\oplus1,y\oplus1,z\oplus1) 的贡献。使得最终的 d(S,S_i) 满足条件。

具体的，统计 i=F_{111},j=F_{110},p=F_{101},q=F_{100} 的个数，使其满足下列不等式：

i+j+p+q>r_1\\ i+j+G_{101}-p+G_{100}-q>r_2\\ i+G_{110}-j+p+G_{100}-q>r_3 \end{cases}

这样就有了 \mathcal{O}(n^4) 的做法：暴力枚举 ，判断其是否合法。注意加入答案时需要乘一个系数 \binom{G_{111}}{i}\binom{G_{110}}{j}\binom{G_{101}}{p}\binom{G_{100}}{q}。

考虑如何优化。发现一次枚举四个很蠢，试一下只枚举两个。枚举 i,j，上面的不等式移项得：

p+q>r_1\\ p+q<i+j+G_{101}+G_{100}-r_2\\ p-q>r_3-i+j-G_{110}-G_{100} \end{cases}

发现 p+q,p-q 的范围都是一个区间。换句话说，如果把 (p+q,p-q) 看成坐标系中的一个点，那么需要统计的区间就是一个矩阵。

都有矩阵了，怎么能没有二维前缀和呢。开始时对于每个 p,q 令 sum_{p+q,p-q}=\binom{G_{101}}{p}\binom{G_{100}}{q}，后面对于每个 i,j 用二维前缀和统计答案即可。

这题有一些细节，比如 p-q 可能是负数，需要加一个极大值作为下标，还要把下标整体加 1 等等。具体实现可以参考代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
int n,S[5],a[10005][5];
int cnt[2][2][2];
int fac[10005],inv[10005];
void init()
{
    fac[0]=inv[0]=fac[1]=inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        fac[i]=1ll*fac[i-1]*i%mod;
        inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    }
    for(int i=2;i<=n;i++) inv[i]=1ll*inv[i-1]*inv[i]%mod;   
}
int C(int x,int y)
{
    return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int sum[20005][10005];
void Add(int &x,int y){x+=y;(x>=mod)&&(x-=mod);}
void Del(int &x,int y){x-=y;(x<0)&&(x+=mod);}
int query(int xx,int xy,int yx,int yy)
{
    if(xx<0||xy<0) return 0;
    if(xx>cnt[1][0][1]+10000||yx>cnt[1][0][1]+10000) return 0;
    yy=max(yy,0);
    xy=min(xy,cnt[1][0][0]+cnt[1][0][1]);
    if(xx<yx||xy<yy) return 0;
    int ret=0;
    Add(ret,sum[xx+1][xy+1]); 
    Del(ret,sum[xx+1][yy]);
    Del(ret,sum[yx][xy+1]);
    Add(ret,sum[yx][yy]);
    return ret;
}
int main()
{
    scanf("%d",&n);init();
    for(int i:{1,2,3})
    {
        scanf("%d",&S[i]);
        for(int j=1;j<=n;j++)
        {
            scanf("%1d",&a[j][i]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int x=a[i][1],y=a[i][2],z=a[i][3];
        if(!a[i][1]) x^=1,y^=1,z^=1;
        cnt[x][y][z]++;
    }
    for(int i=0;i<=cnt[1][0][1];i++)
    {
        for(int j=0;j<=cnt[1][0][0];j++)
        {
            sum[i-j+10001][i+j+1]=1ll*C(cnt[1][0][1],i)*C(cnt[1][0][0],j)%mod;
        }
    }
    for(int i=-cnt[1][0][0];i<=cnt[1][0][1];i++)
    {
        for(int j=0;j<=cnt[1][0][0]+cnt[1][0][1];j++)
        {
            Add(sum[i+10001][j+1],sum[i+10000][j+1]);
            Add(sum[i+10001][j+1],sum[i+10001][j]);
            Del(sum[i+10001][j+1],sum[i+10000][j]);
        }
    }
    int ans=0,tot=1;
    for(int i=1;i<=n;i++) tot=1ll*tot*2%mod;
    for(int i=0;i<=cnt[1][1][1];i++)
    {
        for(int j=0;j<=cnt[1][1][0];j++)
        {
            Add(ans,1ll*C(cnt[1][1][1],i)*C(cnt[1][1][0],j)%mod*
            query(cnt[1][0][1]+10000,cnt[1][0][1]+cnt[1][0][0]+i+j-S[2]-1,S[3]-cnt[1][1][0]-cnt[1][0][0]-i+j+10000+1,S[1]-i-j+1)%mod);
        }
    }
    Del(tot,ans); 
    printf("%d",tot);
}

点个赞再走吧。