频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
数位和乘积(高精组合数学)
2013-02-24 09:46:00      个评论      
收藏   我要投稿
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;  

    }  

    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,rel*C[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]-=i*3;  

            dfs(6,rel*C[n-hasget][i],hasget+i);  

            b[2]+=i*3;  

        }  

    }  

    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]-=i*2;  

            dfs(2,rel*C[n-hasget][i],hasget+i);  

            b[2]+=i*2;  

        }  

    }  

    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<=n;i++)  

        {  

            C[i][0]=C[i][1]=1;  

            for (int j=1;j<=i;j++)  

            {  

                C[i][j]=C[i-1][j]+C[i-1][j-1];        

            }  

        }  

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

  

        for(int i=2;i<=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<<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^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])

 

点击复制链接 与好友分享!回本站首页
上一篇:HDU1159——Common Subsequence
下一篇:hdu 3263 Ancient vending machine
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站