PKU 3989 A hard Aoshu Problem
http://poj.org/problem?id=3989
虫食い算の答えが何通りあるかを答えろというような問題
出現するアルファベット数が少ないので全探索。
リーディングゼロや、異なるアルファベットは異なる数字に気をつける。
int n; string s1,s2,s3; int ctoi[200]; int ans; vector<char> ch; bool ok0(char ch){ return (SZ(s1)==1 || s1[0]!=ch) && (SZ(s2)==1 || s2[0]!=ch) && (SZ(s3)==1 || s3[0]!=ch); } ll stoi(string& s){ ll ret=0; FOR(it,s) ret=ret*10+ctoi[*it]; return ret; } void dfs(int idx,int use){ if(idx==SZ(ch)){ ll i1=stoi(s1),i2=stoi(s2),i3=stoi(s3); if(i1+i2==i3){ //cout<<i1<<'+'<<i2<<'='<<i3<<endl; ++ans; } if(i1-i2==i3){ //cout<<i1<<'-'<<i2<<'='<<i3<<endl; ++ans; } if(i1*i2==i3){ //cout<<i1<<'*'<<i2<<'='<<i3<<endl; ++ans; } if(i2 && i1==i3*i2){ //cout<<i1<<'/'<<i2<<'='<<i3<<endl; ++ans; } return; } rep(i,10){ if((use>>i)&1) continue; if(!i && !ok0(ch[idx])) continue; ctoi[ch[idx]]=i; dfs(idx+1,use|(1<<i)); } } void solve(){ cin>>s1>>s2>>s3; ans=0; set<char> app; FOR(it,s1) app.insert(*it); FOR(it,s2) app.insert(*it); FOR(it,s3) app.insert(*it); ch.clear(); FOR(it,app) ch.pb(*it); dfs(0,0); cout<<ans<<endl; } main(){ cin>>n; rep(i,n) solve(); }