NOIp模拟赛 数字【DP】【背包】【递推】【容斥原理】
点击量: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:20987654321输出样例#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;
}
说点什么