AOJ 2604: Pattern Language

文字ごとに桁数と(2桁なら)一の位が制約つきかを決めて(3^n通りある)
場合わけをひたすらがんばって数えるだけ。
まあ、解いてる人数が少ないだけあってつまらなかった。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[1100];
char in[2];
int u[110];
int mod=1000000007;
int UF[110];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;
	UF[a]+=UF[b];UF[b]=a;
}
char tmp[1100];
int L[110];
int R[110];
int ml[110];
int mr[110];
int pow3[13];
int main(){
	pow3[0]=1;
	for(int i=1;i<13;i++)pow3[i]=pow3[i-1]*3;
	int a,b;
	scanf("%d%d",&a,&b);
	scanf("%s",str);
	for(int i=0;i<b;i++){
		int c;
		scanf("%s%d",in,&c);
		u[in[0]-'a']=c;
	}
	int ret=0;
	for(int i=0;i<pow3[10];i++){
		bool dame=false;
		for(int j=0;j<110;j++)UF[j]=L[j]=R[j]=-1;
		for(int j=0;j<10;j++)ml[j]=mr[j]=0;
		for(int j=0;j<10;j++){
			if(u[j]<10&&(i%pow3[j+1]/pow3[j]))dame=true;
			if(i%pow3[j+1]/pow3[j]==2){
				L[j]=u[j]/10;
				
			}
			if(u[j]<10||i%pow3[j+1]/pow3[j]==2){
				ml[j]=u[j]/10;
				mr[j]=u[j]%10;
			}else{
				if(i%pow3[j+1]/pow3[j])ml[j]=u[j]/10-1;
				else ml[j]=0;
				mr[j]=9;
			}
	//		if(u[j]<20&&(i%pow3[j+1]/pow3[j]==1))dame=true;
		}
		if(dame)continue;
		int sz=0;
		for(int j=0;j<a;j++){
			if('0'<=str[j]&&str[j]<='9')tmp[sz++]=str[j];
			else{
				int p=str[j]-'a';
				if(i%pow3[p+1]/pow3[p]){
					tmp[sz++]='A'+p;
					tmp[sz++]=str[j];
				}else tmp[sz++]=str[j];
			}
		}
		for(int j=0;j<sz;j++){
			if('0'<=tmp[j]&&tmp[j]<='9'){
				if('0'<=tmp[sz-1-j]&&tmp[sz-1-j]<='9'){
					if(tmp[j]!=tmp[sz-1-j])dame=true;
				}else if('A'<=tmp[sz-1-j]&&tmp[sz-1-j]<='Z'){
					if(~L[tmp[sz-1-j]-'A']&&L[tmp[sz-1-j]-'A']!=tmp[j]-'0')dame=true;
					L[tmp[sz-1-j]-'A']=tmp[j]-'0';
				}else{
					if(~R[tmp[sz-1-j]-'a']&&R[tmp[sz-1-j]-'a']!=tmp[j]-'0')dame=true;
					R[tmp[sz-1-j]-'a']=tmp[j]-'0';
				}
			}else if('A'<=tmp[j]&&tmp[j]<='Z'){
				if('A'<=tmp[sz-1-j]&&tmp[sz-1-j]<='Z'){
					UNION(tmp[j]-'A',tmp[sz-1-j]-'A');
				}
				if('a'<=tmp[sz-1-j]&&tmp[sz-1-j]<='z'){
					UNION(tmp[j]-'A',10+tmp[sz-1-j]-'a');
				}
			}else{
				if('a'<=tmp[sz-1-j]&&tmp[sz-1-j]<='z'){
					UNION(tmp[j]-'a'+10,tmp[sz-1-j]-'a'+10);
				}
			}
		}
		for(int j=0;j<10;j++){
			for(int k=0;k<10;k++){
				if(~L[j]&&~L[k]&&FIND(j)==FIND(k)&&L[j]!=L[k])dame=true;
				if(~L[j]&&~R[k]&&FIND(j)==FIND(k+10)&&L[j]!=R[k])dame=true;
				if(~R[j]&&~R[k]&&FIND(j+10)==FIND(k+10)&&R[j]!=R[k])dame=true;
				if(R[k]==0&&FIND(j)==FIND(k+10))dame=true;
				if(L[k]==0)dame=true;
				if(FIND(j)==FIND(k)&&ml[j]<L[k])dame=true;
				if(FIND(j)==FIND(k+10)&&ml[j]<R[k])dame=true;
				if(FIND(j+10)==FIND(k)&&mr[j]<L[k])dame=true;
				if(FIND(j+10)==FIND(k+10)&&mr[j]<R[k])dame=true;
			}
		}
		if(dame)continue;
		long long val=1;
		for(int j=0;j<10;j++){
			if(UF[j+10]<0){
				if(!~R[j]){
					int mv=9;
					int nz=0;
					int one=0;
					for(int k=0;k<10;k++){
						if(FIND(j+10)==FIND(k)){
							if(~L[k])one=1;
							mv=min(mv,ml[k]);
							nz=1;
						}
						if(FIND(j+10)==FIND(k+10)){
							if(~R[k])one=1;
							mv=min(mv,mr[k]);
						}
					}
					//if(one)continue;
					if(one);
					else if(nz)val=val*mv%mod;
					else val=val*(mv+1)%mod;
				}
			}
			if(i%pow3[j+1]/pow3[j]){
				if(UF[j]<0){
					if(!~L[j]){	
						int mv=9;
						int	nz=1;
						int one=0;
						for(int k=0;k<10;k++){
							if(FIND(j)==FIND(k)){
								if(~L[k])one=1;
								mv=min(mv,ml[k]);
								nz=1;
							}
							if(FIND(j)==FIND(k+10)){
								if(~R[k])one=1;
								mv=min(mv,mr[k]);
							}
						}
						if(one);
						else if(nz)val=val*mv%mod;
						else val=val*(mv+1)%mod;
					}
				}
			}
		}
	//	for(int j=0;j<10;j++)printf("%d",i%pow3[j+1]/pow3[j]);
	//	printf(": %lld\n",val);
		ret=(ret+val)%mod;
	}
	printf("%d\n",ret);
}