记录编号	121362	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC2003]平凡的车票	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.698 s
提交时间	2014-09-19 16:20:01	内存使用	26.67 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=40,SIZEL=12,HS=100007,BASE=10000;
int R[11][4]={0};//1~10分解
class HP{
public:
	int len;
	int s[SIZEL];
	void print(void){
		printf("%d",s[len-1]);
		for(int i=len-2;i>=0;i--) printf("%04d",s[i]);
	}
	void clear(void){len=1,memset(s,0,sizeof(s));}
	HP(){clear();}
	void operator = (int x){clear();s[0]=x;}
	void operator += (HP b){
		len=max(len,b.len);
		int i;
		for(i=0;i<len||s[i];i++){
			s[i]+=b.s[i];
			s[i+1]+=s[i]/BASE;
			s[i]%=BASE;
		}
		if(i>len) len=i;
		while(len>1&&!s[len-1]) len--;
	}
	void operator -= (HP b){
		for(int i=0;i<len;i++){
			while(s[i]<b.s[i]) s[i+1]--,s[i]+=BASE;
			s[i]-=b.s[i];
		}
		while(len>1&&!s[len-1]) len--;
	}
};
HP operator * (HP a,HP b){
	HP c;
	c.len=a.len+b.len+1;
	int i;
	for(i=0;i<a.len;i++){
		for(int j=0;j<b.len;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;
		}
	}
	for(i=0;i<c.len||c.s[i];i++) c.s[i+1]+=c.s[i]/BASE,c.s[i]%=BASE;
	if(i>c.len) c.len=i;
	while(c.len>1&&!c.s[c.len-1]) c.len--;
	return c;
}
HP pow(HP s,int n){
	HP ans;ans=1;
	for(int i=1;i<=n;i++) ans=ans*s;
	return ans;
}
class STATE{
public:
	int a[4];//指数
	HP sum;//方案数
	void print(void){
		for(int i=0;i<4;i++) cout<<a[i]<<" ";cout<<"sum: ";sum.print();cout<<endl;
	}
	void clear(void){memset(a,0,sizeof(a)),sum=1;}//初始情况:1有一种
	int hashval(void){
		int ans=0;
		for(int i=0;i<4;i++) ans=(ans*257)+a[i];
		ans%=HS;if(ans<0) ans+=HS;
		ans=(ans*27031LL+30013LL)%HS;
		return ans;
	}
};
bool operator == (STATE &s,STATE &t){
	for(int i=0;i<3;i++) if(s.a[i]!=t.a[i]) return false;
	return true;
}
bool operator != (STATE &s,STATE &t){return !(s==t);}
STATE mul(STATE s,int x){//方案*x
	if(s.a[0]==-1) return s;//0*x=0
	if(x==0) memset(s.a,-1,sizeof(s.a));//s*0=0
	else for(int i=0;i<4;i++) s.a[i]+=R[x][i];
	return s;
}
class HS_TABLE{
public:
	int tot;//0~tot
	STATE st[HS];//st的长度其实可以更小
	int hash[HS];//在st中的下标
	void clear(void){
		tot=0;
		memset(hash,-1,sizeof(hash));
	}
	int find(STATE &s){//返回它在hash中的下标
		int pos=s.hashval();
		while(hash[pos]!=-1&&st[hash[pos]]!=s){
			pos++;
			if(pos==HS) pos=0;
		}
		return pos;
	}
	bool find(STATE &s,STATE &t){
		int pos=find(s);
		if(hash[pos]==-1) return false;
		t=st[hash[pos]];
		return true;
	}
	void insert(STATE s){
		int pos=find(s);
		if(hash[pos]==-1){
			hash[pos]=tot;
			st[tot]=s;
			tot++;
		}
		else st[hash[pos]].sum+=s.sum;
	}
};
void DP(char S[],int N,HS_TABLE f[2]){
	int k=0;
	f[k].clear();
	STATE one;one.clear();
	f[k].insert(one);
	for(int i=0;i<N;i++){
		f[k^1].clear();
		for(int j=0;j<f[k].tot;j++){
			if(S[i]!='?') f[k^1].insert(mul(f[k].st[j],S[i]-'0'));
			else{
				for(int d=0;d<10;d++){
					f[k^1].insert(mul(f[k].st[j],d));
				}
			}
		}
		k^=1;
	}
}
int N;
char S[SIZEN]={0};
HS_TABLE F[2],L[2];//前一半和后一半
int unsure(void){
	int ans=0;
	for(int i=0;i<2*N;i++) ans+=(S[i]=='?');
	return ans;
}
void work(void){
	HP ten,ans1,ans2;
	ten=10,ans1=0,ans2=pow(ten,unsure());
	DP(S,N,F);
	DP(S+N,N,L);
	int k=N&1;
	STATE t;
	for(int i=0;i<F[k].tot;i++)
		if(L[k].find(F[k].st[i],t))
			ans1+=(F[k].st[i].sum*t.sum);
	ans2-=ans1;
	ans1.print();printf("\n");
	ans2.print();printf("\n");
}
void init(void){
	scanf("%d",&N);
	scanf("%s",S);
	for(int i=1;i<=10;i++){
		int x=i;
		while(x%2==0) R[i][0]++,x/=2;
		while(x%3==0) R[i][1]++,x/=3;
		while(x%5==0) R[i][2]++,x/=5;
		while(x%7==0) R[i][3]++,x/=7;
	}
}
int main(){
	freopen("banal.in","r",stdin);
	freopen("banal.out","w",stdout);
	init();
	work();
	return 0;
}