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

1
#include <bits/stdc++.h>
2

3
#define N 62
4
#define MOD 1000000007
5
using namespace std;
6

7
typedef long long ll;
8

9
int numN[N], numM[N];
10
ll f[N][2][2][2][2];
11
int k;
12

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

29
ll calc(ll n, ll m) {
30
    memset(numN, 0, sizeof numN);
31
    memset(numM, 0, sizeof numM);
32
    memset(f, -1, sizeof f);
33

34
    // 进制分解
35
    int size1 = 0, size2 = 0;
36
    ll tmp1 = n, tmp2 = m;
37
    while (tmp1) {
38
        numN[size1++] = tmp1 % k;
39
        tmp1 /= k;
40
    }
41
    while (tmp2) {
42
        numM[size2++] = tmp2 % k;
43
        tmp2 /= k;
44
    }
45
    return dfs(max(size1, size2) - 1, false, true, true, true);
46
}
47

48
int main() {
49
    ios::sync_with_stdio(false);
50
    cin.tie(nullptr);
51
    cout.tie(nullptr);
52

53
    memset(f, -1, sizeof f);
54

55
    int t;
56
    cin >> t >> k;
57
    while (t--) {
58
        ll n, m;
59
        cin >> n >> m;
60
        cout << calc(n, m) << endl;
61
    }
62
    return 0;
63
}