J: Key Storage

Karl is developing a key storage service. Each user has a positive integer key. Karl knows that storing keys in plain text is bad practice. So, instead of storing a key, he decided to store a fingerprint of a key. However, using some existing fingerprint algorithm looked too boring to him, so he invented his own one. Karl’s fingerprint is calculated by the following process: divide the given integer by 2, then divide the result by 3, then divide the result by 4, and so on, until we get a result that equals zero (we are speaking about integer division each time). The fingerprint is defined as the multiset of the remainders of these divisions. For example, this is how Karl’s fingerprint algorithm is applied to the key 11: 11 divided by 2 has remainder 1 and result 5, then 5 divided by 3 has remainder 2 and result 1, and 1 divided by 4 has remainder 1 and result 0. Thus, the key 11 produces the sequence of remainders [1, 2, 1] and has the fingerprint multiset {1, 1, 2} . Ksenia wants to prove that Karl’s fingerprint algorithm is not very good. For example, she found that both keys 178800 and 123456 produce the fingerprint of{0, 0, 0, 0, 2, 3, 3, 4}. Thus, users are at risk of fingerprint collision with some commonly used and easy to guess keys like 123456. Ksenia wants to make her words more persuasive. She wants to calculate the number of other keys that have the same fingerprint as the keys in the given list of some commonly used keys. Your task is to help her. 输入 The first line contains an integer t (1≤t≤50 000) — the number of commonly used keys to examine. Each of the next t lines contains one integer ki (1≤ki≤1018) — the key itself. 输出 For each of the keys print one integer — the number of other keys that have the same fingerprint. 样例输入 Copy 3 1 11 123456 样例输出 Copy 0 1 127 提示 The other key with the same fingerprint as 11 is 15. 15 produces a sequence of remainders [1, 1, 2]. So both numbers have the fingerprint multiset {1, 1, 2}.

题解：这是一道组合计数，给出的num，%2，/2，%3，/3，直到0为止，这样算出来的余数a[2],a[3],a[4]…，顺序可以打乱，因为余数总是这些。但是也有一些限制，比如a[2],是%2的结果，所以在a[2]的位置上绝对不可能>=2。然后从后往前组合计算。

#include<bits/stdc++.h> #include<algorithm> #include<iostream> using namespace std; typedef long long ll; typedef long double lf; typedef pair<int,int>P; const int inf = 0x7f7f7f7f; const int N = 2e6+10; const ll mod = 1e9+7; const double PI = 3.14; int read(){ char ch=getchar();int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int random(int n){return(ll)rand()*rand()%n;} int Mu[N]; ll c[105],b[105]; ll C(ll n,ll m){ ll x = 1,y = 1; for(ll i = 1;i <= m;i++){ x = x*n--; y = y*i; } return x/y; } ll fun(ll num,ll cnt){ memset(c,0,sizeof c); ll ans = 1; if(cnt == 1ll) b[0]--; for(ll i = 30;i >= 0;i--){ if(b[i]){ ll t = num-max(i,1ll);t -= cnt; ans = ans*C(t,b[i]); cnt += b[i]; } } return ans; } void solve(ll num){ ll cnt = 2; vector<ll>a; memset(b,0,sizeof b); while(num){ a.push_back(num%cnt); b[num%cnt]++; num /= cnt; ++cnt; } ll ans = fun(cnt-1,0); //cout<<b[0]<<endl; if(b[0]) ans -= fun(cnt-1,1); cout<<ans-1<<endl; /* sort(a.begin(),a.end()); int sum = -1; do{ int flag = 1; for(int i = 0;i < a.size();i++){if(a[i] >= i+2 || a[a.size()-1] == 0){flag = 0;break;}} if(flag){sum++;} }while(next_permutation(a.begin(),a.end())); cout<<sum<<endl; */ } int main(){ //and((unsigned)time(0)); //freopen("out.txt","w",stdout); //freopen("in.txt","r",stdin); int t = read(); while(t--){ ll num;cin >> num; solve(num); } return 0; }