数位和乘积(高精组合数学)
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;
}
