NOIp模拟赛 数字【DP】【背包】【递推】【容斥原理】

点击量：16

   DP思路有点难想的一个DP套递推题。为啥还要容斥原理

目录

题目描述

一个数字被称为好数字当他满足下列条件：

1. 它有2*n个数位，n是正整数(允许有前导0)。
2. 构成它的每个数字都在给定的数字集合S中。
3. 它前n位之和与后n位之和相等或者它奇数位之和与偶数位之和相等

例如对于n=2,S={1,2}，合法的好数字有 1111、1122,1212,1221,2112,2121,2211,2222这样8种。

 

已知n，求合法的好数字的个数mod 999983。

 

输入输出格式

输入格式：

第一行一个数n。

 

接下来一个长度不超过10的字符串，表示给定的数字集合。

 

输出格式：

一行一个数字表示合法的好数字的个数mod 999983。

 

输入输出样例

输入样例#1：

2

0987654321

输出样例#1：

1240

输入样例#2：

844
01234579

输出样例#2：

364947

说明

对于20%的数据,n≤7。

对于100%的数据,n≤1000,|S|≤10。

   一开始想的是从小段合法向大段扩展的区间DP，发现大段合法小段不一定就合法，于是hack掉了。

   于是发现可用的数字是0~9，一共n个数，那么总和不超过9000（注意不是9999，一开始WA可能错在这里了），因此可以做背包，递推求出每种结果的方案数。

   根据以上的预处理，我们来看题目要求:前半段等于后半段，奇数项等于偶数项。那么我们如果把前半段等于后半段的求出来了，那么奇数项等于偶数项的方案就是一样的，因为我们可以将元素依次插入，像这样：

   因此每对合法数列可以被算两次，我们枚举每个Σ，从0到9×n，平方后乘2，平方的原因是它左边和右边的方案数是乘起来的，而且刚好数值相同。

   不过这样会重复计算，比如数列1 2 2 1，既满足条件1，又满足条件2。因此我们要用容斥原理来排除这些情况，这就是这道题麻烦的地方。因此我们需要构造既满足条件1又满足条件2的情况，来减掉它们。

   我们在上述的递推过程中只保存了和，而没有保存是奇数还是偶数。而这个问题也不用担心，和上面一样的做法，只不过需要考虑n是奇数或偶数的情况。

   我们对这个长度为2n的数列分成4段，长度分别为\(\lfloor \frac n2 \rfloor,\lfloor \frac {n+1}2 \rfloor,\lfloor \frac n2 \rfloor,\lfloor \frac {n+1}2 \rfloor\)，只要第一段+第三段和第二段+第四段（长度分别相等）的和分别相等，那么x1+x2=x3+x4，满足条件1，同时将x3插入x1，x4插入x2，也满足了奇偶相等（条件2）。那么我们只要枚举一/三段长度和二/四段长度就可以了，这里最大复杂度是9000×9000，再加上前面的三维背包枚举，可能会时间超限，不过这种做法可以拿到90分。

   这一段代码：

for(int i=0;i<=l1;i++)//l1是i最大可枚举到的数
    for(int j=0;j<=l2;j++)//l2是j最大可枚举到的数
    {
        sum-=((f[n/2][i]*f[(n+1)/2][j])%999983)*(f[n/2][i]*f[(n+1)/2][j])%999983;
        sum=(sum+999983)%999983;
    }

   我们发现，总是f[][i]在乘f[][j]，那么我们可以分别用O(N)把f[][i]的和以及f[][j]的和求出来，再相乘，这样复杂度降到了O(N)，于是前面有了更大的常数发挥空间（逃。

   改进后的代码：

long long A=0,B=0;
for(int i=0;i<=m1;i++)//此处m1是最大可枚举数，l1是前半段长度
{
    A+=(long long)f[l1][i]*f[l1][i];
    A%=999983;
}
for(int i=0;i<=m2;i++)
{
    B+=(long long)f[l2][i]*f[l2][i];
    B%=999983;
}
sum-=A*B%999983;

   就可以AC了。

   记住一点，这个题有时候乘会爆int，可能有时我们会选择加括号long long，不过有时候括号迭代太多，自己分辨不清导致错误的产生，因此在空间允许的情况下，把数组开long long是最保险的。

Code：

#include<cstdio>
#include<cstring>
int max(int x,int y)
{
    return x>y?x:y;
}
int f[1010][10000];//长度为i,总和为j
char c[12];
int ava[12];
int main()
{
    memset(f,0,sizeof(f));
    int n;
    scanf("%d",&n);
    scanf("%s",c);
    int len=strlen(c);
    for(int i=0;i<len;i++)
        ava[i+1]=c[i]-'0';
    f[0][0]=1;//初始化
    for(int i=1;i<=n;i++)
        for(int k=0;k<=9*n;k++)//注意上界的选择
            for(int j=1;j<=len;j++)
                if(k-ava[j]>=0)
                {
                    f[i][k]+=f[i-1][k-ava[j]];
                    f[i][k]%=999983;
                }
    long long sum=0;
    for(int i=0;i<=9*n;i++)
    {
        sum+=(long long)2*f[n][i]*f[n][i];
        sum%=999983;
    }
    int l1=n>>1,l2=n+1>>1;//两小段的长度
    int m1=9*l1;
    int m2=9*l2;
    long long A=0,B=0;
    for(int i=0;i<=m1;i++)
    {
        A+=(long long)f[l1][i]*f[l1][i];
        A%=999983;
    }
    for(int i=0;i<=m2;i++)
    {
        B+=(long long)f[l2][i]*f[l2][i];
        B%=999983;
    }
    sum-=A*B%999983;
    printf("%lld\n",(sum+999983)%999983);
    return 0;
}