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