组合数问题

题目描述

见https://www.luogu.org/problemnew/show/P3746#sub
数据范围

$1 \leq n \leq 10^9,0 \leq {r - 1} \leq {k - 1} \leq 50,2 \leq p \leq 2^{30} - 1$
题解

良心的30分可以通过组合递推得到。

$p = 2$的时候直接$dp$方案数0或1即可。

$k = 1$的时候显然答案就是$2^n$

$k = 2$的时候答案是$2^{n - 1}$

直到80分你都可以使用逆元$O1$计算组合数。

现在来分析一下题目中的组合数到底代表什么？

其实就是从$n \times k$个物品中，选出$mod$k余$r$的方案数。

考虑$dp$，$dp[i][j]$表示考虑前$i$个物品，选出来的物品数模$k$为$j$的方案数。

方程：$dp_{i + 1,j} = dp_{i,j} + dp_{i,j - 1}$

矩阵优化即可。

复杂度$O(k^3 log_n)$

当然这已经足够通过本题。

我们再来看看这个式子。

可以表示成这个样子：$dp[2n][i + j] += dp[n][i] + dp[n][j]$

可以理解为从前$n$个物品中选$i$的方案数和从后$n$个物品中选$j$个的方案数是从整个

$ 2\times n$中选$i + j$个的方案数。

直接倍增即可，复杂度$O(k^2 log_n)$
```
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
int ret[55], tmp[55], ttt[55], p;
int n, r, k;
void pow_mod(int n) {
	ret[0] = 1;
	if (k == 1) tmp[0] = 2;
	else tmp[0] = tmp[1] = 1;
	while (n) {
		if (n & 1ll) {
			for (int i = 0; i < k; ++i)
				ttt[i] = 0;
			for (int i = 0; i < k; ++i)
				for (int j = 0; j < k; ++j)
					ttt[(i+j)%k] += (ret[i] * tmp[j]) % p;
			for (int i = 0; i < k; ++i)
				ret[i] = ttt[i] % p;
		}
		for (int i = 0; i < k; ++i)
			ttt[i] = 0;
		for (int i = 0; i < k; ++i)
			for (int j = 0; j < k; ++j)
				ttt[(i+j)%k] += (tmp[i] * tmp[j]) % p;
		for (int i = 0; i < k; ++i)
			tmp[i] = ttt[i] % p;
		n >>= 1ll;
	}
}
signed main() {
	scanf("%d %lld %d %d", &n, &p, &k, &r);
	pow_mod(n*k);
	printf("%lld", ret[r]);
}
```

组合数问题

组合数问题

题目描述

数据范围

题解