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

作者: wjyyy 分类: DP,容斥原理,组合数学,背包,解题报告,递推 发布时间: 2018-06-26 17:40

点击量:175

 

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

 

说点什么

avatar
  Subscribe  
提醒
/* */