数位和乘积(高精组合数学)
Problem 3 数位和乘积(digit.cpp/c/pas)
【题目描述】
一个数字的数位和乘积为其各位数字的乘积。求所有的N位数中有多少个数的数位和乘积恰好为K。请注意，这里的N位数是可以有前导零的。比如01，02视为二位数，但是他们的数位和乘积都是0。
【输入格式】
一行两个整数N，K
【输出格式】
一个行一个整数表示结果。
【样例输入】
2 3
【样例输出】
2
【样例输入2】
2 0
【样例输出2】
19
【数据范围】
对于20%：N <= 6。
对于50%：N<=16
存在另外30%：K=0。
对于100%：N <= 50，0 <= K <= 10^9。
法1：
k=0时，ans=10^n-9^n
否则就用记忆化搜索填1..9的个数
#include<cstdio>#include<cstring>#include<algorithm>#include<functional>#include<iostream>#include<cstdlib>#include<cmath>#include<cctype>using namespace std;#define MAXN (50+10)#define F (10000)int n,k;struct highn{int len,a[900];highn():len(1){memset(a,0,sizeof(a));}highn(int x){memset(a,0,sizeof(a));int i=0;while (x){a[++i]=x%F;x/=F;}len=i;}void print(){printf("%d",a[len]);for (int i=len-1;i;i--){//if (a[i]<10000) printf("0");if (a[i]<1000) printf("0");if (a[i]<100) printf("0");if (a[i]<10) printf("0");printf("%d",a[i]);}}friend highn operator+(highn& a,highn& b){highn c;int maxlen=max(a.len,b.len);for (int i=1;i<=maxlen;i++){c.a[i]=c.a[i]+a.a[i]+b.a[i];if (c.a[i]>F){c.a[i+1]+=c.a[i]/F;c.a[i]%=F;}}c.len=maxlen+1;while (!c.a[c.len]&&c.len>1) c.len--; return c;}friend highn operator-(highn& a,highn& b){highn c;int maxlen=a.len;for (int i=1;i<=maxlen;i++){c.a[i]+=a.a[i]-b.a[i];if (c.a[i]<0){c.a[i+1]--;c.a[i]+=F;}}c.len=maxlen;while (!c.a[c.len]&&c.len>1) c.len--; return c;}friend highn operator*(highn& a,highn& b){highn c;for (int i=1;i<=a.len;i++){for (int j=1;j<=b.len;j++){c.a[i+j-1]+=a.a[i]*b.a[j];if (c.a[i+j-1]>F){c.a[i+j]+=c.a[i+j-1]/F;c.a[i+j-1]%=F;}}}c.len=a.len+b.len+1;while (!c.a[c.len]&&c.len>1) c.len--; return c;}};highn pow2(highn a,int b){highn c;if (!b) return 1;if (b%2){c=pow2(a,b/2);c=c*c;c=c*a;} else{c=pow2(a,b/2);c=c*c;}return c;}int a[11],tot,b[11];highn ans,C[51][51];void dfs(int deep,highn rel,int hasget){if (n<hasget) {return;}if (deep==0||n==hasget){for (int i=1;i<=9;i++) if (b[i]) return;ans=ans+rel;return;}else if (deep==9){int m=min(n-hasget,b[3]/2);for (int i=0;i<=m;i++){b[3]-=i*2;dfs(8,rel*C[n-hasget][i],hasget+i);b[3]+=i*2;}}else if (deep==8){int m=min(n-hasget,b[2]/3);for (int i=0;i<=m;i++){b[2]-=i*3;dfs(6,rel*C[n-hasget][i],hasget+i);b[2]+=i*3;}}else if (deep==6){int m=min(n-hasget,min(b[2],b[3]));for (int i=0;i<=m;i++){b[2]-=i;b[3]-=i;dfs(4,rel*C[n-hasget][i],hasget+i);b[2]+=i,b[3]+=i;}}else if (deep==4){int m=min(n-hasget,b[2]/2);for (int i=0;i<=m;i++){b[2]-=i*2;dfs(2,rel*C[n-hasget][i],hasget+i);b[2]+=i*2;}}else{if (b[2]+b[3]+b[5]+b[7]+hasget<=n){int f[4]={2,3,5,7};for (int i=0;i<4;i++){rel=rel*C[n-hasget][b[f[i]]];hasget+=b[f[i]];}ans=ans+rel;return ;}}}int main(){//highn a=1254321,b=7612345;//highn c=pow(a,3);//c.print();freopen("digit.in","r",stdin);freopen("digit.out","w",stdout);scanf("%d%d",&n,&k);if (!k){highn c=pow2(10,n),d=pow2(9,n);highn e=c-d;e.print();}else{memset(a,0,sizeof(a));tot=0;C[0][0]=1;for (int i=1;i<=n;i++){C[i][0]=C[i][1]=1;for (int j=1;j<=i;j++){C[i][j]=C[i-1][j]+C[i-1][j-1];}}//C[16][10].print();for(int i=2;i<=9;i++){while (k%i==0){a[i]++;k/=i;tot++;}}memcpy(b,a,sizeof(a));if (k==1) dfs(9,1,0);ans.print();}cout<<endl;return 0;}f[i][j][k][l][m]表示填到第i个数,2,3,5,7分别用j,k,l,m个的方案数
考虑后面填1..9的情况(显然不可能填0)
Bug：n=50,C(n,m)最大为C(50,25),可用long long.
----
----
法3：
容易发现
k=2^a*3^b*5^c*7^d时才有解
而且5,7取了当且只当数位为5,7的情况.
2-2,4,6,8
3-3,6,9
5-5
7-7
故可只考虑2,3,不考虑5,7
f[i][j]k]表示i位，取了j个2和k个3后的方案数，
因为可以用1填充，
所以答案=∑f[p][j][k]*C(p,j+k)*C(n,a[5])*C(n-a[5],a[7]) (p<=n-a[5]-a[7])