BZOJ 2425 [HAOI2010]计数：数位dp + 组合数

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2425

题意：

　　给你一个数字n，长度不超过50。

　　你可以将这个数字：

　　　　（1）去掉若干个0

　　　　（2）打乱后重新排列

　　问你可以产生多少个小于n的数字。

题解：

　　题目中的第一个操作其实是没有用的。

　　去掉若干个0之后再重新排列（不允许前导0），和不去0直接重新排列（允许前导0），其实是等价的。

　　所以按照数位dp的方法从高到低按位统计。

　　如n = 2345时，分别统计前缀为0~1, 20~22, 230~233, 2340~2344的答案。

　　最高位为第1位。

　　假设当前考虑到第i位，1~i-1位都和原数字n完全匹配。

　　枚举第i位可以填了x∈[0,a[i])，则先让cnt[x]--。

　　然后就是i+1位之后的数如何填了。

　　设len = n-i。

　　方案数 = 先从len个位置中找了cnt[0]个位置全填0的方案数 * 又从(len-cnt[0])个位置中找了cnt[1]个位置全填1的方案数...

　　方案数 = C(len,cnt[0]) * C(len-cnt[0],cnt[1]) * C(len-cnt[0]-cnt[1],cnt[2])...

　　最后再让cnt[x]++回来，然后cnt[a[i]]--就好了。

AC Code:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #define MAX_N 55

 #define MAX_D 15

 using namespace std;

 int n;

 long long ans=;

 long long a[MAX_N];

 long long cnt[MAX_N];

 long long c[MAX_N][MAX_N];

 char s[MAX_N];

 void read()

 {

     scanf("%s",s+);

     n=strlen(s+);

     for(int i=;i<=n;i++) cnt[a[i]=s[i]-'']++;

 }

 void cal_c()

 {

     c[][]=;

     for(int i=;i<=n;i++)

     {

         c[i][]=;

         for(int j=;j<=i;j++)

         {

             c[i][j]=c[i-][j]+c[i-][j-];

         }

     }

 }

 long long cal_p(int len)

 {

     long long now=;

     for(int i=;i<=;i++)

     {

         now*=c[len][cnt[i]];

         len-=cnt[i];

     }

     return now;

 }

 void cal_ans()

 {

     for(int i=;i<=n;i++)

     {

         for(int j=;j<a[i];j++)

         {

             cnt[j]--;

             ans+=cal_p(n-i);

             cnt[j]++;

         }

         cnt[a[i]]--;

     }

 }

 void work()

 {

     cal_c();

     cal_ans();

     printf("%lld\n",ans);

 }

 int main()

 {

     read();

     work();

 }

巴特西

BZOJ 2425 [HAOI2010]计数：数位dp + 组合数

最新文章

热门文章