todo 快速幂 组合数 隔板法 T3 #10231. 「一本通 6.6 练习 2」方程的解 - 题目 - LibreOJ (loj.ac)
题目描述
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 ，其中 是正整数，（即 除以 的余数）， 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当 时，方程的解分别为：
a_1=1\\ a_2=1\\ a_3=2 \end{cases} \ \ \ \ \begin{cases} a_1=1\\ a_2=2\\ a_3=1 \end{cases} \ \ \ \ \begin{cases} a_1=2\\ a_2=1\\ a_3=1 \end{cases} $$ ### 输入格式 有且只有一行，为用空格隔开的两个正整数，依次为 k,x。 ### 输出格式 有且只有一行，为方程的正整数解组数。 ### 样例 #### 输入 ``` 3 2 ``` #### 输出 ``` 3 ``` ### 数据范围与提示 对于 $40\%$ 数据，答案不超过 $10^{16}$； 对于全部数据，$1\le k\le 100,1\le x\lt 2^{31},k\le g(x)$。 ## 思路 $n = x^{x}\mod 1000$ 可以用 qmi 快速幂, 以 $O(\log n)$ 的复杂度求得。 本题中求 $a_{1}+ a_{2} +a_{3}+\dots + a_{k}=n$ 的正整数解数量, 可以映射为小球插隔板问题, 又称隔板法。 $a_{1}+a_2+a_3=4$ 是, 看做有 $4$ 个球 ```mermaid graph 1((1)) 2((1)) 3((1)) 4((1)) ``` 而三个数就对应 $2$ 个隔板, 通过枚举隔板摆放方案, 就可以得出所有解, 其中被隔板分开的每一块球的数量就是对应 $a_i$ 的值。最多有 $1000$ 个球, 故复杂度可以实现。 所有的方案数就是 $C_{n-1}^{k-1}$ , 可惜的是答案没有取模, $10^{16}$ 必须得用高精度, 而我们组合数最多会用到 $C^{100}_{1000}$ , 可以直接用 $f[i][j] = f[i-1][j]+f[i-1][j-1]$ 递推求得。 高精度可以用数组来实现, 最多会用 $\frac{1000!}{100!\times 900!} = 1e150$ , 即 $150$ 位。 ## 代码 ```c++ #include <iostream> #include <cstring> #include <string> #include <algorithm> using namespace std; const int N = 150, M = 100, MOD = 1000; int f[1000][M][N]; int k, n, x; int qmi(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; } void add(int c[], int a[], int b[]) { for(int i = 0, t = 0; i < N; i++) { t += a[i] + b[i]; c[i] = t % 10; t /= 10; } } int main() { cin >> k >> x; n = qmi(x % 1000, x, MOD); 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]); int *g = f[n-1][k-1]; int i = N - 1; while(!g[i]) i--; while(i>=0) cout << g[i--]; return 0; } ```