2013-02-24 09:46:00      个评论

Problem 3 数位和乘积(digit.cpp/c/pas)

【题目描述】

【输入格式】

【输出格式】

【样例输入】

2 3

【样例输出】

2

【样例输入2】

2 0

【样例输出2】

19

【数据范围】

k=0时，ans=10^n-9^n

[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;

}

f[i][j][k][l][m]表示填到第i个数,2,3,5,7分别用j,k,l,m个的方案数

Bug：n=50,C(n,m)最大为C(50,25),可用long long.

----

----

k=2^a*3^b*5^c*7^d时才有解

2-2,4,6,8

3-3,6,9

5-5

7-7

f[i][j]k]表示i位，取了j个2和k个3后的方案数，