题面在这里

description

你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。

比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。

现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.

data range

\[n的长度不超过50，答案不超过2^{63}-1.
\]

solution

题目相当于求将$n$按位拆开重组后小于$n$的数的个数(包含前导0)

考虑数位$DP$,当由危险态到达安全态的时候,由于后面的数码我们已经知道,且可以任意取,

是不是用组合数学统计一下就可以了?

假设当前考虑第$i$位$a_i$并且选出了一个数码$s$代替这一位,

且已经知道不包括第$i$位的后面部分组成数码的个数,存储在$t_{0...9}$中,

那么当前这一位的答案就是$$\sum_{s=0}^{{a_i-1}\frac{(\sum_{k=0}}{9}t[k])!}{\prod_{k=0}^{9}t[k]!}$$

如果你按照这种递推式写代码你会由于爆$long long$获得$60$分的好成绩

所以答案需要转换一下,由于$$\frac{(\sum_{k=0}^{{9}t[k])!}{\prod_{k=0}}{9}t[k]!}=\prod_{k=0}^{{9}C_{\sum_{k=s}}{9}t[k]}^{t[s]}$$

最后把每一位答案相加即可

具体实现的过程中,根本不需要开动态规划数组

code

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#define RG register

#define il inline

using namespace std;

typedef long long ll;

typedef double dd;

typedef vector<int> VI;

const int N=52;

ll n,a[N],t[10],tot,ans,C[N][N];

il ll calc(int x){

  RG ll sum=1,cnt=tot-1;

  for(RG int i=0;i<=9;i++)

    if(t[i]-(i==x))

      sum*=C[cnt][(t[i]-(i==x))],cnt-=(t[i]-(i==x));

  return sum;

}

int main()

{

  RG char ch=0;

  C[0][0]=1;

  for(RG int i=1;i<=50;i++)

    for(RG int j=0;j<=50;j++){

      C[i][j]=C[i-1][j];

      if(j)C[i][j]+=C[i-1][j-1];

    }

  while(ch>'9'||ch<'1')ch=getchar();

  while(ch<='9'&&ch>='0'){a[++n]=ch-48;t[a[n]]++;tot++;ch=getchar();}

  for(RG int i=1;i<=n;tot--,t[a[i]]--,i++)

    for(RG int k=0;k<a[i];k++)

      if(t[k])ans+=calc(k);

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

  return 0;

}

巴特西

[HAOI2010]计数

description

data range

solution

code

最新文章

热门文章