题目大意
有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<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<unordered_map>
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<int>
#define y1 y12345678909
#define rii register int
#define pii pair<int,int>
#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=0,_f=1;char _s=getchar();
while(!isdigit(_s)){if(_s=='-')_f=-1;_s=getchar();}
while(isdigit(_s)){_x=(_x<<3)+(_x<<1)+(_s-'0');_s=getchar();}
return _x*_f;
}
struct mint {
li _[6];
int __;
};
mint operator + (mint _x,mint _y){
int _k;
li _g=0;
mint _z;
for(rii _i=_x.__+1;_i<=5;++_i)_x._[_i]=0;
for(rii _i=_y.__+1;_i<=5;++_i)_y._[_i]=0;
if(_x.__>_y.__)_k=_x.__;
else _k=_y.__;
for(rii _i=1;_i<=_k;++_i){
_z._[_i]=(_x._[_i]+_y._[_i]+_g)%Tot;
_g=(_x._[_i]+_y._[_i]+_g)/Tot;
}
if(_g>0){
_z._[++_k]=_g;
}
_z.__=_k;
return _z;
}
mint operator - (mint _x,mint _y){
int _k;
_k=_x.__;
for(rii _i=_x.__+1;_i<=5;++_i)_x._[_i]=0;
for(rii _i=_y.__+1;_i<=5;++_i)_y._[_i]=0;
for(rii _i=1;_i<=_k;++_i){
if(_x._[_i]<_y._[_i]){
_x._[_i]+=Tot;
_x._[_i+1]--;
}
_x._[_i]-=_y._[_i];
}
while(_k>1&&_x._[_k]==0)_k--;
_x.__=_k;
return _x;
}
mint operator * (mint _x,mint _y){
int _k;
li _g=0;
mint _z;
for(rii _i=_x.__+1;_i<=5;++_i)_x._[_i]=0;
for(rii _i=_y.__+1;_i<=5;++_i)_y._[_i]=0;
_k=_x.__+_y.__-1;
for(rii _i=0;_i<=5;++_i)
_z._[_i]=0;
for(rii _i=1;_i<=_x.__;++_i)
for(rii _j=1;_j<=_y.__;++_j)
_z._[_i+_j-1]+=_x._[_i]*_y._[_j];
for(rii _i=1;_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>1&&_z._[_k]==0)_k--;
_z.__=_k;
return _z;
}
void pr(mint _x){
for(rii _i=_x.__;_i>0;--_i)
if(_i!=_x.__&&_x._[_i]==0){
for(rii _j=1;_j<=9;++_j)cout<<0;
}else if(_i!=_x.__){
li _m=_x._[_i];
int _k=0;
while(_m){
_m/=10;
_k++;
}
for(rii _j=1;_j<=9-_k;++_j)cout<<0;
cout<<_x._[_i];
}
else cout<<_x._[_i];
puts("");
}
//---------------------------------------------------------------------------//
//---------------------------------------------------------------------------//
li dp[2][2][59][40][21][21];
int a[2][19],tot[2],P[19][5],za,zb,now[3];
mint g[19],c[19][19];
inline void init(){
for(rii i=1;i<=9;++i){
int m=i;
while(m%2==0){
P[i][1]++;
m/=2;
}
while(m%3==0){
P[i][2]++;
m/=3;
}
while(m%5==0){
P[i][3]++;
m/=5;
}
while(m%7==0){
P[i][4]++;
m/=7;
}
}
return;
}
inline void Get(){
for(rii i=0;i<=18;++i)
for(rii j=0;j<=18;++j)
c[i][j]._[1]=0,c[i][j].__=1;
c[0][0].__=1;
c[0][0]._[1]=1;
for(rii i=1;i<=18;++i)
c[i][0].__=c[i][0]._[1]=c[i][i].__=c[i][i]._[1]=1;
for(rii i=1;i<=18;++i)
for(rii j=1;j<i;++j)
c[i][j]=c[i-1][j]+c[i-1][j-1];
g[0].__=g[0]._[1]=1;
mint nin;
nin.__=1,nin._[1]=9;
for(rii i=1;i<=18;++i)g[i]=g[i-1]*nin;
}
inline mint pw(mint a,int p){
mint res;
res.__=res._[1]=1;
while(p){
if(p&1)res=res*a;
a=a*a;
p>>=1;
}
return res;
}
inline void deal(){
mint Ans;
Ans.__=1,Ans._[1]=0;
if(za&&!zb){
for(rii i=0;i<=tot[0];++i)
for(rii j=0;j<tot[1];++j)
Ans=Ans+(g[i]*c[tot[0]][tot[0]-i]*g[j]*c[tot[1]][tot[1]-j]);
}else if(!za&&zb){
for(rii i=0;i<tot[0];++i)
for(rii j=0;j<=tot[1];++j)
Ans=Ans+(g[i]*c[tot[0]][tot[0]-i]*g[j]*c[tot[1]][tot[1]-j]);
}else {
for(rii i=0;i<=tot[0];++i)
for(rii j=0;j<=tot[1];++j)
Ans=Ans+(g[i]*c[tot[0]][tot[0]-i]*g[j]*c[tot[1]][tot[1]-j]);
}
pr(Ans);
mint ten;
ten.__=1;
ten._[1]=10;
pr(pw(ten,tot[0]+tot[1])-Ans);
exit(0);
}
mint xx,yy;
inline mint gt(li wh){
mint res;
res.__=0;
while(wh){
res._[++res.__]=wh%Tot;
wh/=Tot;
}
return res;
}
mint ch(li A,li B){
xx=gt(A),yy=gt(B);
return xx*yy;
}
int main(){
freopen("banal.in","r",stdin);
freopen("banal.out","w",stdout);
memset(P,0,sizeof(P));
int n,m;
now[0]=now[1]=0;
tot[0]=tot[1]=0;
za=zb=0;
char s;
init();
Get();
n=ra();
for(rii i=1;i<=n;++i){
cin>>s;
if(s=='?')a[0][i]=-1,tot[0]++;
else a[0][i]=s-'0';
if(s=='0')za++;
}
for(rii i=1;i<=n;++i){
cin>>s;
if(s=='?')a[1][i]=-1,tot[1]++;
else a[1][i]=s-'0';
if(s=='0')zb++;
}
if(za>0||zb>0){
deal();
return 0;
}
clr(dp[0][0]);clr(dp[1][0]);
dp[0][0][0][0][0][0]=dp[1][0][0][0][0][0]=1;
for(int _=0;_<=1;_++)
for(rii i=1;i<=n;++i){
now[_]^=1;
clr(dp[_][now[_]]);
if(a[_][i]!=-1){
for(rii p1=0;p1<=i*3;++p1)
for(rii p2=0;p2<=i*2;++p2)
for(rii p3=0;p3<=i;++p3)
for(rii p4=0;p4<=i;++p4){
int P1=p1+P[a[_][i]][1],P2=p2+P[a[_][i]][2],
P3=p3+P[a[_][i]][3],P4=p4+P[a[_][i]][4];
dp[_][now[_]][P1][P2][P3][P4]=
dp[_][now[_]][P1][P2][P3][P4]+
dp[_][now[_]^1][p1][p2][p3][p4];
}
}else {
for(rii p1=0;p1<=i*3;++p1)
for(rii p2=0;p2<=i*2;++p2)
for(rii p3=0;p3<=i;++p3)
for(rii p4=0;p4<=i;++p4)
for(rii j=1;j<=9;++j){
int P1=p1+P[j][1],P2=p2+P[j][2],P3=p3+P[j][3],P4=p4+P[j][4];
dp[_][now[_]][P1][P2][P3][P4]=
dp[_][now[_]][P1][P2][P3][P4]+
dp[_][now[_]^1][p1][p2][p3][p4];
}
}
}
mint Ans;
Ans.__=1,Ans._[1]=0;
for(rii p1=0;p1<=n*3;++p1)
for(rii p2=0;p2<=n*2;++p2)
for(rii p3=0;p3<=n;++p3)
for(rii p4=0;p4<=n;++p4){
Ans=Ans+ch(dp[0][now[0]][p1][p2][p3][p4],dp[1][now[1]][p1][p2][p3][p4]);
}
for(rii i=0;i<tot[0];++i)
for(rii j=0;j<tot[1];++j)
Ans=Ans+(g[i]*c[tot[0]][tot[0]-i]*g[j]*c[tot[1]][tot[1]-j]);
pr(Ans);
mint ten;
ten.__=1;
ten._[1]=10;
pr(pw(ten,tot[0]+tot[1])-Ans);
return 0;
}