传送门

题目大意

有2*n个位置，这些位置有的已经填上了数，有的还没有（用?表示），现在让你在还没有填上数的填0~9中的任意数，使得前n个数的乘积等于后n个数的乘积，问有多少种方案。

分析

首先这个题 并没有取模，所以我们要使用高精度。在这个题中我为了加速，将朴素的高精度变成了5个long long类型。然后我们将问题分为先考虑填1~9，再单独考虑填0的情况这两个子问题。

1.考虑填1~9

我们首先会想到的自然是dpij表示考虑到第i个数，乘积为j的方案数。但我们们发现由于乘积可能会很大，所以这样是不可行的。于是我们考虑优化，不难发现我们可以将所有1~9之中的数写为2p13p25p37p4的形式，于是推而广之，对于所有这些有1~9的数构成的数都可以写为这个形式。但是由于空间极小，这样还是不行的，然而对于所有i都只与i-1有关，所以我们可以使用滚动数组。然后我们再经过精妙的计算可以发现对于每个dp数组的答案都不会超过long long的范围，所以我们只需要用long long记录，到统计答案时在转化为高精度形式就行了。对于这一部分的答案就是对于每个不同的四元组(p1,p2,p3,p4)所对应的前半段的dp值乘后半段的dp值。

2.考虑填0

对于每一段，我们可以枚举填1~n个0，而这一段的方案数∑C(n,i)9^(n-i)，而最终答案便是前半段求出的值乘上后半段乘上的值。

注意

有可能前半段或者后半段已经填过0了，那我们就要特判这种情况呢，这种情况的计算和考虑填0这一部分的思想相似，只不过可以不填0（即i可以等于0）。

具体实现见代码

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

using namespace std;

#define ct cout
#define el endl
#define fi first
#define se second
#define pf printf
#define li long long
#define pb push_back
#define mkp make_pair
#define vi vector
#define y1 y12345678909
#define rii register int
#define pii pair
#define ck(x) cout<<x<<endl;
#define ui unsigned int
#define clr(x) memset(x,0,sizeof(x))
#define sp cout<<"---------------------------------------------------"<<endl

const li Tot=1e9;

inline int ra(){
int _x=,_f=;char _s=getchar();
while(!isdigit(_s)){if(_s=='-')_f=-;_s=getchar();}
while(isdigit(_s)){_x=(_x<<)+(_x<<)+(_s-'');_s=getchar();} return _x*_f; } struct mint { li _[]; int __; }; mint operator + (mint _x,mint _y){ int _k; li _g=; mint _z; for(rii _i=_x.__+;_i<=;++_i)_x._[_i]=; for(rii _i=_y.__+;_i<=;++_i)_y._[_i]=; if(_x.__>_y.__)_k=_x.__;
else _k=_y.__;
for(rii _i=;_i<=_k;++_i){ _z._[_i]=(_x._[_i]+_y._[_i]+_g)%Tot; _g=(_x._[_i]+_y._[_i]+_g)/Tot; } if(_g>){
_z._[++_k]=_g;
}
_z.__=_k;
return _z;
}
mint operator - (mint _x,mint _y){
int _k;
_k=_x.__;
for(rii _i=_x.__+;_i<=;++_i)_x._[_i]=; for(rii _i=_y.__+;_i<=;++_i)_y._[_i]=; for(rii _i=;_i<=_k;++_i){ if(_x._[_i]<_y._[_i]){ _x._[_i]+=Tot; _x._[_i+]--; } _x._[_i]-=_y._[_i]; } while(_k>&&_x._[_k]==)_k--;
_x.__=_k;
return _x;
}
mint operator * (mint _x,mint _y){
int _k;
li _g=;
mint _z;
for(rii _i=_x.__+;_i<=;++_i)_x._[_i]=; for(rii _i=_y.__+;_i<=;++_i)_y._[_i]=; _k=_x.__+_y.__-; for(rii _i=;_i<=;++_i) _z._[_i]=; for(rii _i=;_i<=_x.__;++_i) for(rii _j=;_j<=_y.__;++_j) _z._[_i+_j-]+=_x._[_i]*_y._[_j]; for(rii _i=;_i<=_k;++_i){ li _a=_z._[_i]+_g; _z._[_i]=_a%Tot; _g=_a/Tot; } while(_g){ _z._[++_k]=_g%Tot; _g/=Tot; } while(_k>&&_z._[_k]==)_k--;
_z.__=_k;
return _z;
}
void pr(mint _x){
for(rii _i=_x.__;_i>;--_i)
if(_i!=_x.__&&_x._[_i]==){
for(rii _j=;_j<=;++_j)cout<<;
}else if(_i!=_x.__){
li _m=_x._[_i];
int _k=;
while(_m){
_m/=;
_k++;
}
for(rii _j=;_j<=-_k;++_j)cout<<;
cout<<_x._[_i];
}
else cout<<_x._[_i];
puts("");
}

//---------------------------------------------------------------------------//
//---------------------------------------------------------------------------//

li dp[][][][][][];
int a[][],tot[],P[][],za,zb,now[];
mint g[],c[][];
inline void init(){
for(rii i=;i<=;++i){ int m=i; while(m%==){ P[i][]++; m/=; } while(m%==){ P[i][]++; m/=; } while(m%==){ P[i][]++; m/=; } while(m%==){ P[i][]++; m/=; } } return; } inline void Get(){ for(rii i=;i<=;++i) for(rii j=;j<=;++j) c[i][j]._[]=,c[i][j].__=; c[][].__=; c[][]._[]=; for(rii i=;i<=;++i) c[i][].__=c[i][]._[]=c[i][i].__=c[i][i]._[]=; for(rii i=;i<=;++i) for(rii j=;j>=;
}
return res;
}
inline void deal(){
mint Ans;
Ans.__=,Ans._[]=;
if(za&&!zb){
for(rii i=;i<=tot[];++i) for(rii j=;j>s;
if(s=='?')a[][i]=-,tot[]++;
else a[][i]=s-'';
if(s=='')za++;
}
for(rii i=;i<=n;++i){ cin>>s;
if(s=='?')a[][i]=-,tot[]++;
else a[][i]=s-'';
if(s=='')zb++;
}
if(za>||zb>){
deal();
return ;
}
clr(dp[][]);clr(dp[][]);
dp[][][][][][]=dp[][][][][][]=;
for(int _=;_<=;_++)
for(rii i=;i<=n;++i){
now[_]^=;
clr(dp[_][now[_]]);
if(a[_][i]!=-){
for(rii p1=;p1<=i*;++p1)
for(rii p2=;p2<=i*;++p2)
for(rii p3=;p3<=i;++p3)
for(rii p4=;p4<=i;++p4){
int P1=p1+P[a[_][i]][],P2=p2+P[a[_][i]][],
P3=p3+P[a[_][i]][],P4=p4+P[a[_][i]][];
dp[_][now[_]][P1][P2][P3][P4]=
dp[_][now[_]][P1][P2][P3][P4]+
dp[_][now[_]^][p1][p2][p3][p4];
}
}else {
for(rii p1=;p1<=i*;++p1)
for(rii p2=;p2<=i*;++p2)
for(rii p3=;p3<=i;++p3)
for(rii p4=;p4<=i;++p4)
for(rii j=;j<=;++j){
int P1=p1+P[j][],P2=p2+P[j][],P3=p3+P[j][],P4=p4+P[j][];
dp[_][now[_]][P1][P2][P3][P4]=
dp[_][now[_]][P1][P2][P3][P4]+
dp[_][now[_]^][p1][p2][p3][p4];
}
}
}
mint Ans;
Ans.__=,Ans._[]=;
for(rii p1=;p1<=n*;++p1)
for(rii p2=;p2<=n*;++p2)
for(rii p3=;p3<=n;++p3)
for(rii p4=;p4<=n;++p4){
Ans=Ans+ch(dp[][now[]][p1][p2][p3][p4],dp[][now[]][p1][p2][p3][p4]);
}
for(rii i=;i<tot[];++i)
for(rii j=;j<tot[];++j)
Ans=Ans+(g[i]*c[tot[]][tot[]-i]*g[j]*c[tot[]][tot[]-j]);
pr(Ans);
mint ten;
ten.__=;
ten._[]=;
pr(pw(ten,tot[]+tot[])-Ans);
return ;
}