数位和乘积(高精组合数学)

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<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&amp; a,highn&amp; b)
{
    highn c;
    int maxlen=max(a.len,b.len);
    for (int i=1;i&lt;=maxlen;i++)
    {
        c.a[i]=c.a[i]+a.a[i]+b.a[i];
        if (c.a[i]&gt;F)
        {
            c.a[i+1]+=c.a[i]/F;
            c.a[i]%=F;
        }
    }
    c.len=maxlen+1;
    while (!c.a[c.len]&amp;&amp;c.len&gt;1) c.len--; 
    return c;

}
friend highn operator-(highn&amp; a,highn&amp; b)
{
    highn c;
    int maxlen=a.len;
    for (int i=1;i&lt;=maxlen;i++)
    {
        c.a[i]+=a.a[i]-b.a[i];
        if (c.a[i]&lt;0)
        {
            c.a[i+1]--;
            c.a[i]+=F;
        }
    }
    c.len=maxlen;
    while (!c.a[c.len]&amp;&amp;c.len&gt;1) c.len--; 
    return c;
}
friend highn operator*(highn&amp; a,highn&amp; b)
{
    highn c;
    for (int i=1;i&lt;=a.len;i++)
    {
        for (int j=1;j&lt;=b.len;j++)
        {
            c.a[i+j-1]+=a.a[i]*b.a[j];
            if (c.a[i+j-1]&gt;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]&amp;&amp;c.len&gt;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=cc;
c=c
a;
}
else
{
c=pow2(a,b/2);
c=cc;
}
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;
}
else if (deep==9)
{
int m=min(n-hasget,b[3]/2);
for (int i=0;i<=m;i++)
{
b[3]-=i
2;
dfs(8,relC[n-hasget][i],hasget+i);
b[3]+=i
2;
}
}
else if (deep==8)
{
int m=min(n-hasget,b[2]/3);
for (int i=0;i<=m;i++)
{
b[2]-=i3;
dfs(6,rel
C[n-hasget][i],hasget+i);
b[2]+=i3;
}
}
else if (deep==6)
{
int m=min(n-hasget,min(b[2],b[3]));
for (int i=0;i<=m;i++)
{
b[2]-=i;b[3]-=i;
dfs(4,rel
C[n-hasget][i],hasget+i);
b[2]+=i,b[3]+=i;
}
}
else if (deep==4)
{
int m=min(n-hasget,b[2]/2);
for (int i=0;i<=m;i++)
{
b[2]-=i2;
dfs(2,rel
C[n-hasget][i],hasget+i);
b[2]+=i2;
}
}
else
{
if (b[2]+b[3]+b[5]+b[7]+hasget<=n)
{
int f[4]={2,3,5,7};
for (int i=0;i<4;i++)
{
rel=rel
C[n-hasget][b[f[i]]];
hasget+=b[f[i]];
}
ans=ans+rel;
return ;
}
}
}
int main()
{
// highn a=1254321,b=7612345;
// highn c=pow(a,3);
// c.print();
freopen("digit.in","r",stdin);
freopen("digit.out","w",stdout);
scanf("%d%d",&n,&k);
if (!k)
{
highn c=pow2(10,n),d=pow2(9,n);
highn e=c-d;
e.print();
}
else
{

    memset(a,0,sizeof(a));
    tot=0;
    C[0][0]=1;
    for (int i=1;i&lt;=n;i++)
    {
        C[i][0]=C[i][1]=1;
        for (int j=1;j&lt;=i;j++)
        {
            C[i][j]=C[i-1][j]+C[i-1][j-1];      
        }
    }

// C[16][10].print();

    for(int i=2;i&lt;=9;i++)
    {
        while (k%i==0)
        {
            a[i]++;
            k/=i;
            tot++;
        }
    }
    memcpy(b,a,sizeof(a));
    if (k==1) dfs(9,1,0);
    ans.print();
}
cout&lt;&lt;endl;
return 0;

}
法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^a3^b5^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])