CF1267K Key Storage 题解

· · 题解

前言。

所谓的简单组合计数题卡了我一下午。我是真被样例中的这个 127 搞吐了。

翻译题意：
卡尔正在开发一种密钥存储服务。每个用户都有一个正整数密钥。卡尔知道，用纯文本存储密钥是不好的做法。因此，他决定不存储密钥，而是存储密钥的指纹。

卡尔的指纹是这么计算的：对给定的整数先除以 2 然后再除以 3 再除以 4 一直除下去直到结果为 0 为止。

举个例子，例如 11 是这么计算的：

密钥的余数集合就是 \left[1,2,1\right] 的样子。

有人认为用户的密钥很可能和最容易猜的密钥的指纹重合，即产生相同指纹。她想计算出给定的常用密钥列表中的每个密钥有多少个同样指纹的其他密钥。

分析。

前置知识：一是组合数预处理二是组合数的原理然后阅读以下题解。

我们假定排序过后的余数序列 A 称为不在乎顺序的余数序列，将排序前的余数序列 B 称为在乎顺序的余数序列。

我们发现，对于任意一个序列 B 其对应的数一定是唯一的，因为它就是一步步计算得来的，有固定的顺序。也就是说，我们只需要考虑将一个序列 B 进行任意顺序的打乱后能得到的方案数。此时就很明显是组合数学了。

但是如果最后一个余数为 0 即可以整除则该序列 B 不满足要求，这类情况要被特判掉。那么我们现在的问题就是如何计算方案数：

假定一个情况，然后反证。

因为一个数模 p 的余数肯定比 p 小，所以越大的数有越少的选择。那么我们可以假定先取小一些的余数，但是又出现一个问题，就是我们没有办法确定这些小余数的位置，是否在大余数可以取到的位置上出现，这样就没有办法实时维护。做法伪了。

所以为了便于计算，我们就反其道而行之，考虑大余数，再考虑小余数。这样因为余数越大时，其可能包含的余数越大，则后选择的数的范围一定比最先选择的数的范围要大。

那么此时假设之前已经被抢占了 N 个数，而且当前整个余数的序列长度为 L 的同时，假设计算的当前余数为 i 且当前已经抢占的余数的个数为 tot_i 个。则有 C_{L-N-i}^{tot_i} 个可能的方案数。然后去维护抢占的数 N 和当前的余数 i 即可。在此过程中，我们可以考虑最后一个余数为 0 的情况，然后去掉它。

显然我们每次询问都要计算一次，考虑到数据范围，所以要预处理组合数。组合数可以用 C_n^m=C_{n-1}^m+C_{n-1}^{m-1} 处理。因为要找的是与当前数列余数序列相同的数的方案数，所以要排除掉输入序列的情况。

代码如下，仅供参考：

#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
ll t,k;
ll cnt,ans;
ll tot[30],sum[30][30];
ll work(ll chdu){
    ll res=1,sed=0;
    for (int i=chdu;i>=1;i--){
        ll q=chdu-i-sed;
        if(q<tot[i]){
            return 0;
        }
        if(tot[i]){
            res*=sum[q][tot[i]];
            sed+=tot[i];
        }//公式计算。
    }
    return res;
}
void init(){
    sum[0][0]=1;
    for (int i=1;i<=25;i++){
        sum[i][0]=sum[i][i]=1;
    }
    for(int i=1;i<=25;i++){
        for(int j=1;j<i;j++){
            sum[i][j]=sum[i-1][j]+sum[i-1][j-1];
        }
    }
}//预处理。
int main(){
    init();
    cin>>t;
    while(t--){
        cnt=2;
        memset(tot,0,sizeof(tot));
        cin>>k;//多测不清空，样例过不去。
        while(k){
            tot[k%cnt]++;
            k/=cnt;
            cnt++;
        }
        ans=work(cnt-1);
        if(tot[0]){
            tot[0]--;
            ans-=work(cnt-2);
        }
        ans--;//特判掉自己。
        cout<<ans<<"\n";
    }
    return 0;
}

后记。

注意小细节，有缜密的思路，然后看看数据范围，这道题还是不难解决的。

大家如有疑问，可以在评论区提出，我会尽力解答的。