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

· · 题解

发现 n, m 都很大，正常求组合数没法做，而 k 是一个质数，所以考虑使用 Lucas 定理：

\binom{n}{m} \equiv \binom{\lfloor\frac{n}{k}\rfloor}{\lfloor\frac{m}{k}\rfloor} \times \binom{n \bmod k}{m \bmod k} \pmod{k}

上面那个式子显然是一个 k 进制拆分的式子，如果把 n,m 都写作 k 进制的形式，n 的第 i 位（最低位为第一位）为 bn_i，m 的第 i 位为 bm_i，则有：

\binom{n}{m} \equiv \prod_{i} \binom{bn_i}{bm_i} \pmod{k}

显然，如果 \binom{n}{m} 是 k 的倍数，那么它在模 k 意义下肯定等于 0。观察上面这个连乘的式子，显然如果有一项为 0，结果就是 0。因为对于 \forall i, 0 \le bn_i, bm_i < k，那么 \binom{bn_i}{bm_i} = 0 当且仅当 bn_i < bm_i。

所以，问题就转化为了：给定 n, m，求有多少组数对 i, j，满足 1 \le i \le n, 1 \le j \le \min(i, m)，且 i, j 都写作 k 进制形式至少有一位 i 的数值比 j 小。

于是可以设计出一个数位 dp，用 f(cur, \text{ok, dif, fn, fm}) 来表示当前处理到第 cur 位，目前有没有出现某一位数值 i<j，目前 i 与 j 是不是出现了差异（也就是最高 cur 位 i, j 是不是完全相同），目前 i 与 n 是不是出现了差异，目前 j 与 m 是不是出现了差异。转移显然，为了方便使用记忆化搜索实现。

代码仅供参考。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
const int LOGN = 66;
LL k, n, m, bn[LOGN], bm[LOGN];
LL f[LOGN][2][2][2][2];
LL Solve(int cur, bool ok, bool dif, bool fn, bool fm)
{
    if(!cur) return ok;
    LL &res = f[cur][ok][dif][fn][fm];
    if(~res) return res;
    res = 0;
    int upn = fn ? k - 1 : bn[cur], upm = fm ? k - 1 : bm[cur];
    for(int i = 0; i <= upn; i++)
        for(int j = 0; (j <= i || dif) && j <= upm; j++)
            res = (res + Solve(cur - 1, ok | (i < j), dif | (i != j), fn | (i < upn), fm | (j < upm))) % MOD;
    return res;
}
int main()
{
    int t;
    scanf("%d %lld", &t, &k);
    while(t--)
    {
        scanf("%lld %lld", &n, &m);
        memset(f, -1, sizeof f);
        LL mx = max(n, m), len = 0;
        while(mx) mx /= k, len++;
        for(int i = 1; i <= len; i++) bn[i] = n % k, n /= k;
        for(int i = 1; i <= len; i++) bm[i] = m % k, m /= k;
        printf("%lld\n", Solve(len, false, false, false, false));
    }
    return 0;
}