显示代码纯文本
#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
typedef long long LL;
using namespace std;
const int BASE=10000000;
char str[40];
class miku
{
public:
int n;
LL s[8];
miku()
{
n=1;memset(s,0,sizeof(s));
}
void inline operator =(const int a)
{
n=1;
memset(s,0,sizeof(s));
s[0]=a;
}
void inline operator +=(const miku a)
{
n=max(n,a.n)+1;
for(int i=0;i<min(n,a.n);i++)
{
s[i]+=a.s[i];
while(s[i]<0)
{
s[i]+=BASE;
s[i+1]--;
}
s[i+1]+=s[i]/BASE;
s[i]%=BASE;
}
while(n>1&&s[n-1]==0) n--;
}
bool inline operator ==(const int a)
{
if(n==1&&s[0]==a) return 1;
return 0;
}
void print()
{
printf("%d",s[n-1]);
for(int i=n-2;i>=0;i--) printf("%07d",s[i]);
printf("\n");
}
};
inline miku operator *(miku a,miku b)
{
miku c;
c.n=a.n+b.n+1;
for(int i=0;i<=a.n;i++)
{
for(int j=0;j<=b.n;j++)
{
c.s[i+j]+=a.s[i]*b.s[j];
c.s[i+j+1]+=c.s[i+j]/BASE;
c.s[i+j]%=BASE;
}
}
while(c.n>1&&!c.s[c.n-1]) c.n--;
return c;
}
LL s[70000];
miku pow10[40];
bool co[60][40][20][20]={0};
int cnt=0,N;
map<LL,miku> mp[2][2];
vector<LL> q[2];
int pos=0;
LL sb=1;
int cl(int x,int y)
{
int ans=0;
while(x%y==0)
{
ans++;
x/=y;
}
return ans;
}
void bfs(int x,int y,int z,int p,LL now)
{
if(co[x][y][z][p]) return;
co[x][y][z][p]=1;
s[++cnt]=now;
for(int i=2;i<=9;i++)
{
if(now*i<=sb) bfs(x+cl(i,2),y+cl(i,3),z+cl(i,5),p+cl(i,7),now*i);
}
}
void DP(int x)
{
int i,m;
if(x==0) i=1,m=N;
else i=N+1,m=2*N;
int be=0,k=0;
q[be].clear();
for(;i<=m;i++)
{
k=be^1;
char c=str[i-1];
mp[x][k].clear();
q[k].clear();
if(c=='0')
{
for(int j=0;j<q[be].size();j++) mp[x][k][0]+=mp[x][be][q[be][j]];
if(i==1||i==N+1) mp[x][k][0]=1;
q[k].push_back(0);
}
else if('1'<=c&&c<='9')
{
LL p=c-'0';
for(int j=0;j<q[be].size();j++)
{
LL tem=q[be][j];
mp[x][k][p*tem]+=mp[x][be][tem];
q[k].push_back(p*tem);
}
if(i==1||i==N+1) mp[x][k][p]=1,q[k].push_back(p);
//cout<<x<<" "<<k<<" "<<q[k].size()<<" "<<mp[x][k][p]<<endl;
}
else if(c=='?')
{
for(int j=0;j<=9;j++)
{
if(i==1||i==N+1)
{
if(mp[x][k][j]==0) q[k].push_back(j);
mp[x][k][j]=1;
}
for(int mo=0;mo<q[be].size();mo++)
{
LL tem=q[be][mo];
if(mp[x][k][j*tem]==0) q[k].push_back(j*tem);
mp[x][k][j*tem]+=mp[x][be][tem];
}
}
pos++;
}
be=k;
//cout<<q[k].size()<<endl;
}
}
int main()
{
freopen("banalticket.in","r",stdin);
freopen("banalticket.out","w",stdout);
pow10[0]=1;
miku tem;
tem=10;
pow10[1]=pow10[0]*tem;
for(int i=1;i<=36;i++) pow10[i]=pow10[i-1]*tem;
scanf("%d",&N);
for(int i=1;i<=N;i++) sb*=10;
scanf("%s",str);
s[0]=0;
bfs(0,0,0,0,1);
DP(0);DP(1);
miku ans;
ans=0;
int p=N&1;
/*for(int i=0;i<=cnt;i++)
{
cout<<s[i]<<" "<<mp[0][p][s[i]]<<" "<<mp[1][p][s[i]]<<endl;
}*/
for(int i=0;i<=cnt;i++) ans+=mp[0][p][s[i]]*mp[1][p][s[i]];
//cout<<cnt<<endl;
ans.print();
tem=-1;
ans=ans*tem;
miku ans2;
ans2=ans;
ans2+=pow10[pos];
ans2.print();
return 0;
}
mikumikumi