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

您已获得最佳的阅读体验！

题目地址：P6669

看到超大组合数对质数取模首先考虑朴素定理，定理内容如下：

其中第一项可以继续递归。但是这里要涉及到定理的另外一个意义——发现这个公式实质上是在对进行进制分解。整个组合数可以看作是将转换为进制后对位求组合数然后累乘得到的，即：

其中为在进制下位数的最大值，若位数不够则将该位看作。

如果一个数要是的倍数，那么这个数模的结果一定是。根据定理，在连乘过程中，必须至少出现一个零项，最终结果才会是。根据组合数在时结果为的性质，可知我们需要统计进制下有多少有至少一个位严格大于，此时同时对数位 DP 即可。

#include <bits/stdc++.h>

#define N 62
#define MOD 1000000007
using namespace std;

typedef long long ll;

int numN[N], numM[N];
ll f[N][2][2][2][2];
int k;

ll dfs(int pos, bool valid, bool limitN, bool limitM, bool limitI) {
//     当前位   是否已合法   i顶到上界n   j顶到上界m   j顶到上界i
    if (pos < 0) return valid;
    if (f[pos][valid][limitN][limitM][limitI] >= 0) return f[pos][valid][limitN][limitM][limitI]; // 记忆化搜索
    ll sum = 0;
    for (int i = 0; i <= (limitN ? numN[pos] : k - 1); i++) {
        // 枚举 i 在这一位上填的数字
        for (int j = 0; j <= min((limitM ? numM[pos] : k - 1), (limitI ? i : k - 1)); j++) {
            // 枚举 j 在这一位上填的数字，注意需要满足 j 不超过 i 和 m 的最小值
            sum = (sum + dfs(pos - 1, valid | (j > i), limitN & (i == numN[pos]), limitM & (j == numM[pos]),limitI & (i == j))) % MOD;
        }
    }
    f[pos][valid][limitN][limitM][limitI] = sum;
    return sum;
}

ll calc(ll n, ll m) {
    memset(numN, 0, sizeof numN);
    memset(numM, 0, sizeof numM);
    memset(f, -1, sizeof f);

    // 进制分解
    int size1 = 0, size2 = 0;
    ll tmp1 = n, tmp2 = m;
    while (tmp1) {
        numN[size1++] = tmp1 % k;
        tmp1 /= k;
    }
    while (tmp2) {
        numM[size2++] = tmp2 % k;
        tmp2 /= k;
    }
    return dfs(max(size1, size2) - 1, false, true, true, true);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    memset(f, -1, sizeof f);

    int t;
    cin >> t >> k;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        cout << calc(n, m) << endl;
    }
    return 0;
}

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

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