E. Bus Number, C++ (gcc)

E. Bus Number

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

vector<int> cur(10, 0), dig(10, 0);

ll fact[20];

ll arrange(){
    ll den = 1, tot = 0;
    /*for(int j = 0; j < 10; j++) if(cur[j]) cout << j << " : " << cur[j] << " , ";
    cout << endl;*/
    for(int j = 0; j < 10; j++) den *= fact[cur[j]], tot += cur[j];
    return (fact[tot]/den);
}

ll solve(int pos){
    if(pos < 0){
        ll way = 0;
        for(int j = 1; j < 10; j++)
            if(cur[j]){
                cur[j]--;
                way += arrange();
                cur[j]++;
            }
        return way;
    }
    ll ans = 0;
    if(dig[pos] == 0) return solve(pos-1);
    int t = dig[pos];
    for(int j = 1; j <= t; j++){
        cur[pos] = j;
        ans += solve(pos-1);
    }
    return ans;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    fact[0] = 1;
    for(int j = 1; j < 20; j++) fact[j] = fact[j-1]*j;
    ll x;
    cin >> x;
    
    ll t = x, len = 0;
    while(t){
        len++;
        dig[t%10]++;
        t /= 10;
    }
    cout << solve(9) << endl;
    return 0;
}


run \| edit \| history \| help	0