Submission #1189142

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
/*{{{*/  //template
#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define pb push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define all(v) ALL(v)
#define sz(x) (int)(x).size()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
//struct fin{ fin(){ cin.tie(0); ios::sync_with_stdio(false); } } fin_;
struct Double{ double d; explicit Double(double x) : d(x){} };
ostream& operator<<(ostream& os,const Double x){ os << fixed << setprecision(20) << x.d; return os; }
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }
template<typename T,typename U> ostream& operator<<(ostream& os,const pair<T,U>& p){ os << "(" << p.first << ","<< p.second <<")"; return os; }
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); }
 
constexpr ll mod = 1e9+7;
const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1};
/*}}}*/

class UF{
    public:
        vector<int> rank,parent;
        UF(int n){
            rank.resize(n,0);
            parent.resize(n,0);
            for(int i=0;i<n;i++){
                parent[i]=i;
                rank[i]=0;
            }
        }
        int find(int x){
            if(parent[x]==x) return x;
            else return parent[x]=find(parent[x]);
        }
        void unite(int x,int y){
            x=find(x);
            y=find(y);
            if(x==y) return;
            if(rank[x]<rank[y]){ parent[x]=y; }
            else{
                parent[y]=x;
                if(rank[x]==rank[y]) rank[x]++;
            }
        }
        bool same(int x,int y){return find(x)==find(y);}
};

int main(){
    int N;
    string s1,s2;
    cin>>N>>s1>>s2;


    UF uf(256);
    rep(i,N) uf.unite(s1[i],s2[i]);

    ll ans=1;
    set<int> used;
    rep(i,N){
        if(isdigit(s1[i]) and isdigit(s2[i])) continue;
        if(isalpha(s1[i])){
            if(used.count(uf.find(s1[i]))) continue;
            bool f=false;
            for(int j='0';j<='9';j++) if(uf.same(s1[i],j)) f=true;
            if(!f){
                ans*=10;
            }
            used.insert(uf.find(s1[i]));
        }else{
            if(used.count(uf.find(s2[i]))) continue;
            bool f=false;
            for(int j='0';j<='9';j++) if(uf.same(s2[i],j)) f=true;
            if(!f){
                ans*=10;
            }
            used.insert(uf.find(s2[i]));
        }
    }

    if(isalpha(s1[0]) or isalpha(s2[0])){
        ans = ans * 9 / 10;
    }
    cout << ans << endl;
}

Submission Info

Judge Result