专栏文章

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

WWilliamFranklin
P6669题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5snch
此快照首次捕获于
2025/12/01 21:02
3 个月前
此快照最后确认于
2025/12/01 21:02
3 个月前
查看原文
感觉自己很傻。

Solution

直接考虑 Lucas 定理，(nm)≡(⌊np⌋⌊mp⌋)(n mod pm mod p)(modp)\binom{n}{m} \equiv \binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\binom{n\bmod p}{m \bmod p} \pmod p，那么我们就可以将 nn 和 mm 转为 pp 进制，然后数位 dp 即可。
套路的，我们设 fi,0/1,0/1,kf_{i, 0/1, 0/1, k} 表示前 ii 位，n′n' 是否卡着限制，m′m' 是否卡着限制，(n′m′) mod p\binom{n'}{m'}\bmod p 为 kk 的方案数。
转移是简单的，时间复杂度 O(Tk3log⁡kn)O(Tk^3\log_k{n})。
考虑一个很呆的优化：因为 pp 为质数，所以只需要判断是否存在 (n′m′)=0\binom{n'}{m'} = 0 即可。所以我们直接将最后一维改为 0/10/1 表示是否  mod p\text{}\bmod p 为 00 即可。
时间复杂度 O(Tk2log⁡kn)O(Tk^2\log_k{n})。
AC CodeCPP
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
typedef unsigned long long ull;
const int N = 65, M = 105, mod = 1e9 + 7;
int k;
long long n, m;
ull f[2][2][2][2];
int C[M][M];
void Add(ull &x, ull y) {
	x = (x + y) % mod;
}
ull quickpow(ull a, ull b, int mod) {
	ull res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
ull work(long long n, long long m) {
	ull ans = 0;
	ull A = m % mod, B = max(0ll, m - n) % mod, N = (A - B + 1 + mod) % mod;
	ans = mod - (A + B) % mod * N % mod * quickpow(2, mod - 2, mod) % mod;
	vector<int> numn, numm;
	while (n) numn.push_back(n % k), n /= k;
	while (m) numm.push_back(m % k), m /= k;
	int len = max(numn.size(), numm.size());
	while (numn.size() < len) numn.push_back(0);
	while (numm.size() < len) numm.push_back(0);
	reverse(range(numn)), reverse(range(numm));
	int flag = 0;
	memset(f, 0, sizeof(f));
	f[0][1][1][0] = 1;
	For(i, 0, len - 1) {
		memset(f[flag ^ 1], 0, sizeof(f[flag ^ 1]));
		For(l, 0, 1) {
			For(a, 0, k - 1) {
				For(b, 0, k - 1) {
					int V = (l || C[a][b] == 0);
					if (a == numn[i] && b == numm[i]) Add(f[flag ^ 1][1][1][V], f[flag][1][1][l]);
					if (a == numn[i]) Add(f[flag ^ 1][1][0][V], f[flag][1][0][l]);
					if (a == numn[i] && b < numm[i]) Add(f[flag ^ 1][1][0][V], f[flag][1][1][l]);
					if (b == numm[i]) Add(f[flag ^ 1][0][1][V], f[flag][0][1][l]);
					if (b == numm[i] && a < numn[i]) Add(f[flag ^ 1][0][1][V], f[flag][1][1][l]);
					if (a < numn[i] && b < numm[i]) Add(f[flag ^ 1][0][0][V], f[flag][1][1][l]);
					if (a < numn[i]) Add(f[flag ^ 1][0][0][V], f[flag][1][0][l]);
					if (b < numm[i]) Add(f[flag ^ 1][0][0][V], f[flag][0][1][l]);
					Add(f[flag ^ 1][0][0][V], f[flag][0][0][l]);
				}
			}
		}
		flag ^= 1;
	}
	For(i, 0, 1) For(j, 0, 1) Add(ans, f[flag][i][j][1]);
	return ans;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int T = 1;
	cin >> T >> k; 
	while (T--) {
		cin >> n >> m;
		For(i, 0, M - 1) {
			C[i][0] = 1;
			For(j, 1, i) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % k;
		}
		cout << work(n, m) << '\n';
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...