CS Academy 71E.Losing Nim-dp+容斥

题意：

如果一个包含i个可重复元素的数组合法，那么这个数组中每个元素的取值范围是[1,n]，这i个元素的和为n，异或和为0。

给出一个数n，对于 i=[1,n] ，求包含i个可重复元素的数组的方案数，对p取模

n<=500,p<=2^30

Solution：

一个简单的想法就是 f[i][j][k] 表示前i位，和为j，异或和为k的方案数，然后进行 O(n) 转移

但是复杂度是 O(n4) 的，无法满足要求

发现优化不了，那么我们考虑转换状态：原先状态中的k这一维，我们需要的只有k=0这个状态，其他状态对于答案来说有很多都是赘余的，所以我们尝试用二进制来搞：首先我们枚举集合中的元素个数k， f[i][j] 表示只考虑前i个二进制位，和为j，异或和为0的方案数。

转移即为在下一位选取偶数个1： f[i][j]=∑p=0C2pkf[i−1][j−2i−1∗2p]

这样的转移复杂度看似每一次 O(n2) ，实际上是 O(n) 的 (n+n2+n4+...=2∗n)

所以我们的总复杂度为 O(n3logn)

然后这就完了？

如果大家只按照上面的写法去写这道题的话，写完后就会发现这是错的：这种转移可能导致我们最终的得到的序列中有0，所以我们需要去除这些不合法的情况：计算i时会涉及到i-1+1个0，i-2+2个0….

那么一个简单的容斥就出来了，假设 ans[i] 为最终的答案,len为n的二进制位数

那么 ans[i]=f[len][n]−∑i−1j=1Ci−jians[j]

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,mod,f[10][510];
int C[510][510];
int ans[510];
int main()
{
    scanf("%d%d",&n,&mod);
    C[0][0]=1;
    for (int i=1;i<=n;i++)
    {
        C[0][i]=1;
        for (int j=1;j<=n;j++)
            C[j][i]=(C[j][i-1]+C[j-1][i-1])%mod;
    }
    int x=n,len=0;
    while (x) len++,x>>=1;
    for (int i=1;i<=n;i++)
    {
        memset(f,0,sizeof(f));
        f[0][0]=1;
        for (int j=1;j<=len;j++)
            for (int k=0;k<=n;k++)
            {
                for (int p=0;p<=i;p+=2)
                {
                    if (k-p*(1<<j-1)>=0) f[j][k]=(1ll*f[j][k]+1ll*C[p][i]*f[j-1][k-p*(1<<j-1)])%mod;
                    else break;
                }
            }
        ans[i]=f[len][n];
        for (int j=1;j<=i-1;j++)
        {
            ans[i]=(1ll*ans[i]-1ll*ans[j]*C[i-j][i])%mod;
            if (ans[i]<0) ans[i]+=mod;
        }
        printf("%d\n",ans[i]);
    }
}