隔板法求组合数问题
考虑问题:$a_1 + a_2 + … + a_k = n$,要求$a_i(i=1,2,…,k)$都是正整数
共有多少种$\{a_1,a_2,…,a_k\}$ 的组合能够满足上述方案
隔板法
构造n个小球* * * * * * *
,则$n$个小球共有$n-1$个空隙
每插入一个空隙,从该空隙向左直到遇到第一个板子或左边界为止的这个区间的和,记为该数$a_i$的值
则一共插入$k-1$个板子,就可以把原区间分成 $k$ 个子区间,每个子区间的和也就刚好对应了原来的 $k$ 个数
例如: $n=7,k=4$时* *|* *|* *|*
是一种方案,对应了$\begin{cases}a_1=2\\\a_2=2\\\a_3=2\\\a_4=1\end{cases}$
则方案的总数为:$C_{n-1}^{k-1}$
本题思路是
- 快速幂求$n=x^x$
- 隔板法求出组合数$C_{n-1}^{k-1}$
本题答案没有要求取模,答案上界的极限是 $C_{1000}^{100} \approx 10^{143}$ 必爆 $\mathrm{int}和\mathrm{long long}$
需要手写高精度(具体参考基础课求组合数的方法:高精度+递推)
#include <iostream>
using namespace std;
const int N = 150, mod = 1000;
int k, x;
int f[1000][100][N];
int qmi(int a, int b) {
int res = 1;
for (int i = b; i; i >>= 1) {
if (i & 1) res = res * a % mod;
a = a * a % mod;
}
return res;
}
// 高精度 a = b + c
void add(int a[N], int b[N], int c[N]) {
for (int i = 0, t = 0; i < N; ++ i) {
t += b[i] + c[i];
a[i] = t % 10;
t /= 10;
}
}
int main() {
cin >> k >> x;
//求n = x^x
int n = qmi(x % mod, x);
//求组合数C(n-1,k-1)
//递推式C(i,j) = C(i-1,j-1) + C(i-1,j)
for (int i = 0; i < n; ++ i) {
for (int j = 0; j <= i && j < k; ++ j) {
if (!j) f[i][j][0] = 1;
else add(f[i][j], f[i - 1][j], f[i - 1][j - 1]);
}
}
//输出答案C(n-1,k-1)
int it = N - 1;
while (!f[n - 1][k - 1][it]) -- it;
while (it >= 0) cout << f[n - 1][k - 1][it -- ];
return 0;
}
请教一下,f[1000][100][N]这个三维数组存的具体是啥,每一维度代表什么意思?
前两位是组合数,后一位是高精度
__int128可以解决高精度的问题吗
好像不行 __int128最大只能到10^127
上py!
__int128指的是2^128,只有10^39
请教下这里 j <= i && j < k 改成j <= i && j <= k 就会出错为什么?
问下大佬!
数组开小了,改成 f[1000][101][N];
挺好的