这道题的难点在于 \(k|C_{i}^{j}\) 这个特殊限制。
由于 \(n,m\) 的范围很大，再加上式子中有组合数，我们自然而然地想到了 \(\text{lucas}\) 定理：
\[C_{n}^{m}={C_{\lfloor\frac{n}{k}\rfloor}^{\lfloor\frac{m}{k}\rfloor}\times C_{n\%k}^{m\%k}}\pmod k \]不难发现这是一个 \(k\) 进制下的形式。再由于 \(k\) 是质数，所以最终 \(k|C_{i}^{j}\) 当且仅当某一个 \(C_{n\%k}^{m\%k}=0\)。
考虑直接在 \(k\) 进制下数位 \(\text{DP}\)。记 \(f_{x,y,b1,b2,b3}\) 为当前从高到低考虑到了第 \(x\) 位，前面那些位里是(\(y=1\))否(\(y=0\))已经有元素满足 \(C_{n\%k}^{m\%k}=0\)，\(i\) 是(\(b1=1\))否(\(b1=0\))抵到上界，\(j\) 是(\(b2=1\))否(\(b2=0\))抵到上界，\(j\) 是 \(b3=1\) 否 \(b3=0\) 抵到 \(i\) 的大小。
转移比较套路，这里不作赘述。
状态数 \(O(\log k\times 2^4)\)，单词转移复杂度为 \(O(k^2)\)，总时间复杂度为 \(O(T\times \log k\times 2^4\times k^2)\)，可以通过。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
typedef long long ll;
const int N = 66, K = 110, mod = 1e9 + 7;
int k, t, t2, a[N], b[N], C[K][K];
ll n, m, f[N][2][2][2][2];
ll F(int x, int y, int b1, int b2, int b3){
if(!x) return y;
if(~f[x][y][b1][b2][b3]) return f[x][y][b1][b2][b3];
int rn = b1? a[x] : k - 1; ll s = 0;
FL(i, 0, rn){
int rm = min((b3? i : k - 1), (b2? b[x] : k - 1));
FL(j, 0, rm){
s += F(x - 1, (y || !C[i][j]), (b1 && i == a[x]), (b2 && j == b[x]), (b3 && i == j));
s %= mod;
}
}
return f[x][y][b1][b2][b3] = s;
}
void solve(){
scanf("%lld%lld", &n, &m);
memset(f, -1, sizeof(f)), t = t2 = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
ll tmp = n;
while(tmp) a[++t] = tmp % k, tmp /= k;
tmp = m;
while(tmp) b[++t2] = tmp % k, tmp /= k;
printf("%lld\n", F(max(t, t2), 0, 1, 1, 1));
}
int main(){
int T; scanf("%d%d", &T, &k);
FL(i, 0, k){
C[i][0] = 1;
FL(j, 1, i){
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % k;
}
}
while(T--) solve();
return 0;
}