自动搬运

查看原文

来自洛谷，原作者为

	syksykCCC 相信并抓住那些源于热爱，忠于自我的每一个可能性

搬运于2025-08-24 22:22:56，当前版本为作者最后更新于2020-07-22 23:19:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

发现 $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;
}