数位和乘积(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时，答案是n位数中至少有一个的方案数。根据容斥原理就是总的方案数-n位数中一个0也没有的方案数，即10^n-9^n。因为n<=50，要高精度乘、减

2、k!=0时，先分解质因数。如果有2、3、5、7以外的质因数，肯定无解。因为k是各位乘起来的积，不可能出现有一位是11、13之类

然后保存2、3、5、7的指数（设为m2、m3、m5、m7）

令f[i][j][k][l][m]表示前i位凑出j个2、k个3、l个5、m个7的方案数

然后转移就是枚举第i位是1到9的转移（好麻烦啊不想写在这里了……看我代码）

根据计算因为k<=10e，所以只要开数组f[55][30][20][14][12]就差不多了

这样每个f依然要高精度……MLE啦……所以还要滚动数组或者像一维背包dp的做法一样倒着for就可以省掉第一维

（哇啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊因为我的高精数组清0刚好少算一位就wa了只有90不开心啊啊啊啊啊啊啊啊啊啊）

#include
     
      #include
      
       #define mx 50#define LL long longstruct gaojing{	int len;	int a[mx+10];}f[30][20][14][12]; int n,k;inline int max(int a,int b){return a>b?a:b;}inline int min(int a,int b){return a
       
        =1;i--)printf("%d",a.a[i]);	printf("\n");}inline void addi(gaojing a,gaojing b,gaojing &c){	set0(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]>=10)          {              c.a[i+1]+=c.a[i]/10;            c.a[i]%=10;        }    }      c.len=maxlen+1;      while (!c.a[c.len]&&c.len>1) c.len--;}inline void jian(gaojing a,gaojing b,gaojing &c){	set0(c);	for (int i=1;i<=b.len;i++)	  {	  	c.a[i]=a.a[i]-b.a[i];		if (c.a[i]<0)	  	{	  		c.a[i]+=10;	  		int now=i+1;			while (!a.a[now])	  		{	  			a.a[now]=9;	  			now++;	  		}	  		a.a[now]--;	  	}	  }	for (int i=b.len+1;i<=a.len;i++)c.a[i]=a.a[i];	c.len=a.len;	while (c.a[c.len]==0&&c.len>1)c.len--;}inline void mult(gaojing a,gaojing b,gaojing &c){	set0(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];	int mxlen=a.len+b.len+3;	for (int i=1;i<=mxlen;i++)	  {	  	c.a[i+1]+=c.a[i]/10;	  	c.a[i]%=10;	  }	while (c.a[mxlen]==0)mxlen--;	c.len=mxlen;}const int prime[5]={0,2,3,5,7};int num[5];int main(){	freopen("digit.in","r",stdin);	freopen("digit.out","w",stdout);	scanf("%d%d",&n,&k);	if (k==0)//若k=0，方案数为10^n-9^n 	{		gaojing sum;set0(sum);		gaojing tomul;set0(tomul);		gaojing decs;set0(decs);		sum.len=1;sum.a[1]=1;		tomul.len=1;tomul.a[1]=9;		decs.len=n+1;decs.a[n+1]=1;		for(int i=1;i<=n;i++)mult(sum,tomul,sum);		jian(decs,sum,sum);		put(sum);		return 0;	}	for (int i=1;i<=4;i++)	  while (k%prime[i]==0)	  {	  	k/=prime[i];	  	num[i]++;	  }	if (k!=1)	{		printf("0");		return 0;	}	f[0][0][0][0].a[1]=1;f[0][0][0][0].len=1;	for (int i=0;i<=num[1];i++)	for (int j=0;j<=num[2];j++)	for (int k=0;k<=num[3];k++)	for (int l=0;l<=num[4];l++)	f[i][j][k][l].len=1;	for (int i=1;i<=n;i++)	  {	  	int m2=min(num[1],3*i);	  	int m3=min(num[2],2*i);	  	int m5=min(num[3],i);	  	int m7=min(num[4],i);	  	for (int j=m2;j>=0;j--)	  	for (int k=m3;k>=0;k--)	  	for (int l=m5;l>=0;l--)	  	for (int m=m7;m>=0;m--)	  	{ 　　　　　　　　　　if (j>=1)addi(f[j][k][l][m],f[j-1][k]  [l]  [m]  ,f[j][k][l][m]);//2 　　　　　　　　　　if (k>=1)addi(f[j][k][l][m],f[j]  [k-1][l]  [m]  ,f[j][k][l][m]);//3 　　　　　　　　　　if (j>=2)addi(f[j][k][l][m],f[j-2][k]  [l]  [m]  ,f[j][k][l][m]);//4 　　　　　　　　　　if (l>=1)addi(f[j][k][l][m],f[j]  [k]  [l-1][m]  ,f[j][k][l][m]);//5 　　　　　　　　　　if (j&&k)addi(f[j][k][l][m],f[j-1][k-1][l]  [m]  ,f[j][k][l][m]);//6 　　　　　　　　　　if (m>=1)addi(f[j][k][l][m],f[j]  [k]  [l]  [m-1],f[j][k][l][m]);//7 　　　　　　　　　　if (j>=3)addi(f[j][k][l][m],f[j-3][k]  [l]  [m]  ,f[j][k][l][m]);//8 　　　　　　　　　　if (k>=2)addi(f[j][k][l][m],f[j]  [k-2][l]  [m]  ,f[j][k][l][m]);//9	  	}	  }	put(f[num[1]][num[2]][num[3]][num[4]]);}