P6669 [清华集训 2016] 组合数问题 题解

· · 题解

观察题目，显然没办法直接判断是否 k \mid \begin{pmatrix} i \\ j \end{pmatrix}，观察是否能转化。根据组合数公式可以转化为 k \mid \cfrac{i!}{j!(i - j)!}，因为 k 为质数，那么想要能整除，那么分子因数 k 的个数一定要大于分母因数 k 的个数，这样最后才能留下至少一个 k 在结果里。如果定义 [n]_k 为在 n 的质因数分解中包含 k 的个数，例如 [50]_5 = 2，因为 50 = 5 \times 5 \times 2。那么上述条件转化为 [i!]_k > [j!]_k + [(i - j)!]_k。

继续观察条件是否能继续化简，因为自定义的符号依然不好处理。正难则反，如果我们先考虑不能整除，那么应该满足 [i!]_k = [j!]_k + [(i - j)!]_k，因为实际上组合数满足对于同一质因数，分子包含的个数大于等于分母包含的个数，因为组合数一定为整数，如果分子的个数小于分母的，那么就多出了一个无法消掉的质因数，因此肯定满足大于等于。那么观察是否能将逆条件进行处理。

为了优秀的计算 [n!]_k，设 \lfloor x \rfloor 表示对 x 向下取整，则可以得到以下推论。

\varphi^i(n,k) = \begin{cases}n & i = 0 \\\lfloor\cfrac{\varphi^{i-1}(n,k)}{k}\rfloor & i \ge 1 \\\end{cases} [n!]_k = \sum_{i=1}^{+\infty} \varphi^i(n,k)

这个式子很好理解，如果 n = 120 且 k = 5，那么显然答案为 28，因为可以将贡献分层，5^1 给答案贡献一次，5^2 给答案贡献两次，此时 \varphi^i(n,j) 就是计算 k^i 的贡献，此时可以看成类似于单次加一，所以后面的 i 还需要再继续加，类似于先给所有贡献 \ge 1 的 +1，再给 \ge 2 的 +1，一直累加到最后就能统计所有的贡献。比如还是看案例，所有 5^1 都贡献了一个，例如 \{5,10,15,20,...,120\}，总共贡献了 \lfloor \cfrac{n}{k} \rfloor = \varphi^1(120,5)，然后在里面 5^2 包含了 \{25,50,75,100\}，这四个数在第一次少算了一次贡献，因为这里面每个数字都有两个因子 5，所以还要再加，后面同理。因为当 i 超过一定范围时，\varphi^i(n,k) 就会恒等于零，因此不需要计算到 +\infty。

显然上式对 \varphi^i(n,k) 有化简公式，即下式。

\varphi^i(n,k) = \lfloor \cfrac{n}{k^i} \rfloor

那么假设数字 n 的 k 进制表示为 (a_ta_{t-1}...a_1a_0)_k，设 A_u 表示 (a_ta_{t-1}...a_{u+1}a_u)_k，例如 A_{t-1} 表示 (a_ta_{t-1})_k，那么引入勒让德定理，即 A_i = \varphi^i(n,k)，证明在此不过多阐述，好奇的可以自己尝试证明或自行查找。那么可以简化 [n!]_k 的计算为下式。

[n!]_k = \sum_{i=1}^t A_i

那么借助上面的定义，我们假设在要求内取数字 i 和 j，定义 i 和 j 在 k 进制下的表示分别为 (a_ta_{t-1}...a_1a_0)_k 和 (b_tb_{t-1}...b_1b_0)_k，因为在组合数中还出现了 i - j 这一项，那么我们再假设 i - j 在 k 进制下的表示为 (c_tc_{t-1}...c_1c_0)_k。那么实际上逆条件 [i!]_k = [j!]_k + [(i - j)!]_k 可以根据引理转化为下式，其中与小写字母对应大写字母运算的定义与上文相同。

\sum_{i=1}^t A_i = \sum_{i=1}^t B_i + \sum_{i=1}^t C_i

那么进一步化简条件，其实上式等价为下式。

\forall u \in [1,t],A_u = B_u + C_u

证明：因为 [i!]_k = [j!]_k + [(i - j)!]_k，记此条件为已知条件，那么如果取前 u 位，其中 u \in [1,t]，那么 A_u \ge B_u + C_u，因为如果 A_u < B_u + C_u，那么 [i!]_k < [j!]_k + [(i - j)!]_k，因为高位对大小的决定优先级高于低位，但与已知条件不符，因此 A_u \ge B_u + C_u。因为已知 \sum_{i=1}^t A_i = \sum_{i=1}^t B_i + \sum_{i=1}^t C_i，那么每一个不等式的等号都要成立，因为如果有一个不满足，那么左式一定大于右式，显然不成立，因此 \forall u \in [1,t],A_u = B_u + C_u 成立。

并不难证明，上式可以继续转化得到下式，注意上式与下式的字母大小写区别。

\forall u \in [0,t],a_u = b_u + c_u

证明：任意在范围内取 i，那么由已证明或已知式子可得 A_i = B_i + C_i 且 A_{i - 1} = B_{i - 1} + C_{i - 1}，又因为 A_{i - 1} = A_ia_{i-1}，其中右侧二者运算可看为拼接，那么 A_ia_{i-1} = B_ib_{i-1} + C_ic_{i-1}，那么因为 A_i = B_i + C_i，那么因为拼接后依然满足等式，那么拼接的内容也一定满足等式，因此 \forall u \in [0,t],a_u = b_u + c_u 成立。

那么理解上式，可以得到对于每一位 b_i 和 c_i，可以直接相加得到 a_i，即不存在进位的情况，那么等价为 c_i = a_i - b_i 做减法的时候不存在借位，即在已知 i 和 j 时计算 k 进制下的 i - j 不存在借位的情况。

综合上述引理及推论，得到 k \nmid \begin{pmatrix} i \\ j \end{pmatrix} 等价于已知 i 和 j 时计算 k 进制下的 i - j 不存在借位。实际上这就是库默尔定理的一种特殊推论，如果了解的话可以直接使用。

那么我们已经大幅度简化了题目的已知条件，接下来只需要进行数位动态规划即可。那么题目变成了如果要求逆条件，那么我要在 [0,n] 的范围内填 k 进制下的 i，在 [0,\min(i,m)] 的范围内填 k 进制下的 j，分别设为 (a_ta_{t-1}...a_1a_0)_k 和 (b_tb_{t-1}...b_1b_0)_k，那么要满足 \forall i\in [0,t],a_i \ge b_i 才能保证不借位。那么考虑将 n 和 m 转化为 k 进制数，从高位往低位填，记录 flag1 表示 i 填的数保证 i < n_p 还是 i = n_p，分别用 0 和 1 来表示这两种情况，其中 n_p 表示 n 从前向后连接到与当前正在决定的位置相同的位置。同理记录 flag2 表示 j 和 m_p 的关系。所以定义状态 dp_{p,flag1,flag2} 表示当前还剩 p 位没确定且现在的状态是 flag1 和 flag2 的值所对应的状态，因为要保证每一位 a_u \ge b_u，所以 i \ge j，因此不需要考虑这个限制。所以可以直接枚举两个位置都填了什么，flag 可以根据目前枚举的状态转移。其中注意初始状态 dp_{tot,1,1} = 1，其中 tot 表示 n 的位数，因为初始一个数也没有，目前 n_p 和 m_p 都为零，所以目前的 i 和 j 的值都分别与 n_p 和 m_p 相等为零，因此初始状态为此，且值为 1，因为初始有一种不选的情况。还有一些需要判断能否转移的细节，当 i 超过 n_p 或 j 超过 m_p 时不能转移。当前的状态可以从上一个状态转移。

在计算前我们要知道，这里计算的答案是原答案在全集里的补集，因为我们所计算的内容是逆条件，那么计算前还需要全集是什么。因为出现了 \min(i,m)，那么我们分类讨论二者的大小关系。

综上，答案总数有 \frac{(m + 2)(m + 1)}{2} + (n - m)(m + 1)，因为最后的 flag 可以任意取，那么根据容斥得到最终答案为 \frac{(m + 2)(m + 1)}{2} + (n - m)(m + 1) - dp_{0,0,0} - dp_{0,1,0} - dp_{0,0,1} - dp_{0,1,1}。注意如果 n < m 则不存在第二种情况。

总算法时间复杂度为 O(Tn^2\log_k n)，其中 O(\log_k n) 为单次将 n 和 m 转化为 k 进制的时间复杂度数量级，其中因为枚举 flag 的值对于每一个 flag 只有两种情况，因此作为常数省略。总空间复杂度约为 O(\log_k n)，flag 维度所占空间同理作为常数省略。

别忘记取模，千万记得每一个都取模，多测别忘记清空，注意数据范围。注意当 n < m 时第二种情况不存在，且应以 \min(n,m) 代替 m 来防止 n < m 的情况导致累加过度。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod = 1e9 + 7;
int t,k;
int n,m;
int tot;
int res,ans;
int a[105],b[105];//n和m的k进制拆分
int dp[105][2][2];
void init(){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(dp,0,sizeof(dp));
    tot = 0;
    res = ans = 0;
    m = min(n,m);//防止n < m
    int numa = n,numb = m;
    while(numa != 0){
        a[++ tot] = numa % k;
        b[tot] = numb % k;
        numa /= k;
        numb /= k;
    }
    dp[tot][1][1] = 1;
}
signed main(){
    cin >> t >> k;
    while(t --){
        cin >> n >> m;
        init();
        for(int i=tot-1;i>=0;i--){
            for(int flag1=0;flag1<=1;flag1++){
                for(int flag2=0;flag2<=1;flag2++){
                    if(!dp[i + 1][flag1][flag2]) continue;//上一个情况不成立
                    //枚举放什么
                    for(int l=0;l<k;l++){
                        if(flag1 && l > a[i + 1]) continue;//如果已经取等，这一位还更大，那么说明如果取到这个就比n_i大了，因此不合法
                        for(int r=0;r<=l;r++){//要满足不借位就要满足填的不比i填的大
                            if(flag2 && r > b[i + 1]) continue;//如果已经取等，这一位还更大，那么说明如果取到这个就比m_i大了，因此不合法
                            dp[i][flag1 && (l == a[i + 1])][flag2 && (r == b[i + 1])] += dp[i + 1][flag1][flag2];
                            dp[i][flag1 && (l == a[i + 1])][flag2 && (r == b[i + 1])] %= mod;
                        }
                    }
                }
            }
        }
        res = (m + 1) % mod * ((m + 2) % mod) % mod * ((mod + 1) / 2) % mod + (n - m) % mod * ((m + 1) % mod) % mod;
        res %= mod;
        for(int flag1=0;flag1<=1;flag1++){
            for(int flag2=0;flag2<=1;flag2++){
                ans += dp[0][flag1][flag2];
                ans %= mod; 
            }
        }
        cout << ((res - ans) % mod + mod) % mod << endl;
    }
    return 0;
}