数字( 计数dp(starstar ))
- 时限:(1s) 内存:(256M)
Descrption
- 一个数字被称为好数字当他满足下列条件:
- 它有 (2*n) 个数位,(n) 是正整数(允许有前导 (0) )。
- 构成它的每个数字都在给定的数字集合 (S) 中。
- 它前 (n) 位之和与后 (n) 位之和相等或者它奇数位之和与偶数位之和相等。
- 例如对于 (n=2, S={1,2}),合法的好数字有 (1111,1122,1212,1221,2112,2121,2211,2222) 这样 (8) 种。
- 已知 (n),求合法的好数字的个数 (mod 999983)。
Input
- 第一行一个数 (n)。
- 接下来一个长度不超过 (10) 的字符串,表示给定的数字集合(不存在重复的数字)。
Output
- 一行,一个整数表示合法的好数字的个数 (mod 999983)。
Sample Input
2
0987654321
Sample Output
1240
Hint
- 对于 (20\%) 的数据,(n≤7)。
- 对于 (100\%) 的数据,(n≤1000, |S|≤10)。
- 来源:(20180719)
分析
-
对于 (20\%) 的数据,暴力整整就行。
-
对 (100\%) 数据我们用 (dp) 加容斥。
-
令:$ dp[i][j]$ 表示长度为 (i) 且所有数字和为 (j) 的方案数。则有:
[dp[i][j]=sum_{j=0}^{i*Max\_a_i}sum_{k=1}^{len(s) } dp[i-1][j-a[k]] ] -
对于方案数我们分两种情况考虑:
-
前 (n) 与后 (n) 和相同:将和相等,且个数为 (n) 的两个序列拼在一起即可,方案数为:
[ans+=sum_{i=0}^{n*Max\_a_n} (dp[n][i])^2 ] -
奇数位上的数的和与偶数位上的数的和相等:这种情况也可以通过两个长度为 (n) ,且和相等的序列拼在一起,所以方案数和 (1) 一样。
-
-
但是上面的两种方案是有重复的情况的,即存在既符合情况 (1) ,也符合情况 (2) 的序列。
-
设左边奇数序列为 (s_1) ,偶数序列为 (s_2) ,那右边构造为奇数序列为 (s_2),偶数序列为 (s_1) ,则把这种情况减去即可。
[ans-=sum_{i=0}^{frac {n+1}{2}*Max\_a_n}(dp[frac{n+1}{2}][i])^2 * sum_{j=0}^{frac{n}{2}*Max\_a_n}(dp[frac{n}{2}][j])^2 ] -
前 (n) 位数里,奇数位个数有 (frac{n+1}{2}) 个,偶数位个数有 (frac{n}{2}) 个,(Max\_a_n) 表示给出的集合的最大数,其实这里可以直接有 (9) 代替。
-
Code
#include <bits/stdc++.h>
const int maxn=1e3+5,Mod=999983;
typedef long long LL;
LL dp[maxn][9*maxn];
int n,a[11];
void Init(){
char s[11];scanf("%d%s",&n,s+1);
a[0]=strlen(s+1);
for(int i=1;i<=a[0];++i)
a[i]=s[i]-48;
}
void Solve(){
dp[0][0]=1;
for(int i=1;i<=n;++i)//i个数
for(int j=0;j<=i*9;++j)//i个数和为j,最大为i个9
for(int k=1;k<=a[0];++k)
if(j>=a[k])
dp[i][j]=(dp[i][j]+dp[i-1][j-a[k]])%Mod;
LL ans=0;
for(int i=0;i<=n*9;++i)//方案1,2之和
ans=(ans+2*dp[n][i]*dp[n][i])%Mod;
int len1=(n+1)/2,len2=n/2;
LL ans1=0,ans2=0;
for(int i=0;i<=len1 * 9;++i)//长度为(n+1)/2的奇数位序列的组合数
ans1=(ans1+dp[len1][i]*dp[len1][i]%Mod)%Mod;
for(int i=0;i<=len2 * 9;++i)//长度为n/2偶数位序列组合数
ans2=(ans2+dp[len2][i]*dp[len2][i]%Mod)%Mod;
ans=(ans-ans1*ans2%Mod+Mod)%Mod;
printf("%lld
",ans);
}
int main() {
Init();
Solve();
return 0;
}