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的個數 [cpp] #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; } 法2： 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])
