洛谷-2518 [HAOI2010]计数

题目描述
你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.
输入格式
只有1行，为1个整数n.
输出格式
只有整数，表示N之前出现的数的个数。

输入输出样例
输入 #1
1020

输出 #1
7

说明/提示
n的长度不超过50，答案不超过2⁶³-1.

解释：类似数位$dp$,现在有$n$位，$0,1,2,3,..9$等数个数分别是$a[0],a[1],...a[9]$,则排列个数为
$C(n,a[0])\ast C(n-a[0],a[1])\ast .....C(n-a[0]-a[1]...a[8],a[9])$所以我们可以对第i位枚举，然后排列组合就好了

#include
using namespace std;
long long c[1003][1003]={0};
long long C(int n,int m){if(m==0||n==m) return 1LL;if(c[n][m]) return c[n][m];return c[n][m]=C(n-1,m-1)+C(n-1,m);
}
char str[123];
int nn=0,n=0;
int H[123]={0};
long long ret=0;
long long ok(){int m=nn;long long ans=1;for(int i=0;i<10;i++){if(H[i]){ans*=C(m,H[i]);m-=H[i];}}return ans;
}
int main(){cin>>(str+1);for(int i=1;str[i];i++){H[str[i]-'0']++;n++;nn++;}for(int i=1;i<=n;i++){int y=str[i]-'0';nn--;for(int j=0;j

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！