「NOIP模拟赛」数位和乘积
「题目描述」
一个数字的数位和乘积为其各位数字的乘积。求所有的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。
题解
若K=0
10^n-9^n高精度
若K！=0
将K分解质因数，如果有2357以外的就无解
如果只有2357就可以dp了f[i][a1][a2][a3][a4] 前i为2357分别用了a1,a2,a3,a4个
然后加个高精度
为了不爆内存可以使用滚动数组或者做01背包
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,k,t; int a1,a2,a3,a4; int a[32][20][20][12][105]; int x[105],y[105],ans[105]; void add(int *a,int *b) { for(int i=1;i<=100;i++) a[i]+=b[i]; for(int i=1;i<=100;i++) a[i+1]+=a[i]/10,a[i]%=10; } void mul(int *a,int x) { for(int i=1;i<=100;i++) a[i]*=x; for(int i=1;i<=100;i++) a[i+1]+=a[i]/10,a[i]%=10; } void sub(int *a,int *b,int *ans) { for(int i=100;i;i--) ans[i]=a[i]-b[i]; for(int i=1;i<=100;i++) if(ans[i]<0)ans[i]+=10,ans[i+1]--; } void solve() { int t; x[1]=y[1]=1; for(int i=1;i<=n;i++) { mul(x,9); mul(y,10); } sub(y,x,ans); t=100; while(!ans[t])t--; for(int i=t;i;i--) printf("%d",ans[i]); } int main() { //freopen("digit.in","r",stdin); //freopen("digit.out","w",stdout); n=read();k=read(); if(k==0){solve();return 0;} t=k;while(t%2==0)t/=2,a1++; while(t%3==0)t/=3,a2++; while(t%5==0)t/=5,a3++; while(t%7==0)t/=7,a4++; if(t!=1){puts("0");return 0;} a[0][0][0][0][1]=1; for(int i=1;i<=n;i++) for(int x=a1;x>=0;x--) for(int y=a2;y>=0;y--) for(int z=a3;z>=0;z--) for(int l=a4;l>=0;l--) { if(x-1>=0)add(a[x][y][z][l],a[x-1][y][z][l]); if(x-2>=0)add(a[x][y][z][l],a[x-2][y][z][l]); if(x-3>=0)add(a[x][y][z][l],a[x-3][y][z][l]); if(y-1>=0)add(a[x][y][z][l],a[x][y-1][z][l]); if(y-2>=0)add(a[x][y][z][l],a[x][y-2][z][l]); if(x-1>=0&&y-1>=0)add(a[x][y][z][l],a[x-1][y-1][z][l]); if(z-1>=0)add(a[x][y][z][l],a[x][y][z-1][l]); if(l-1>=0)add(a[x][y][z][l],a[x][y][z][l-1]); } int t=100; while(!a[a1][a2][a3][a4][t])t--; for(int i=t;i;i--) printf("%d",a[a1][a2][a3][a4][i]); return 0; } |
Subscribe
计数器 9854361
OI 课件=>
OI 课件=>