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
#include
#include
#include
#include
#include
#include
#include
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
法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])