「NOIP模拟赛」数位和乘积

2014年9月13日3,5460

「题目描述」

一个数字的数位和乘积为其各位数字的乘积。求所有的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背包

 

avatar
  Subscribe  
提醒