重庆家政网站建设,南京企业网站开发费用申请,制作网站软件排行榜,wordpress图片显示缩略图文章目录 隔板法#xff08;求解的组数#xff09;隔板法扩展 例题 隔板法#xff08;求解的组数#xff09;
文章首发于我的个人博客#xff1a;欢迎大佬们来逛逛
隔板法
隔板法能够解决的问题#xff1a;
求线性不定方程的解的组数求相同元素分组的方案数 给我们 … 文章目录 隔板法求解的组数隔板法扩展 例题 隔板法求解的组数
文章首发于我的个人博客欢迎大佬们来逛逛
隔板法
隔板法能够解决的问题
求线性不定方程的解的组数求相同元素分组的方案数 给我们 n n n 个球 k k k 个盒子要求把这些球放进这些盒子中一共有多少种不同的放的方案数 例如 n 4 k 3 n4k3 n4k3 方案如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IUTQYuPA-1685533049927)(%E9%9A%94%E6%9D%BF%E6%B3%95%EF%BC%88%E6%B1%82%E8%A7%A3%E7%9A%84%E7%BB%84%E6%95%B0%EF%BC%89%206f4140365b494c00a1407852acf8dd57/Untitled.png)]
容易看出我们可以划分为 1 1 2 ; 1 2 1; 2 1 1 三种不同的方案。
我们可以把这个问题转换为这样的一个模型
在 x i 1 x_i1 xi1 的条件下求 x 1 x 2 x 3 . . . x k n x_1x_2x_3...x_kn x1x2x3...xkn 的方程解的组数
即在这个问题中方程的解的组数就是 ( x 1 , x 2 , x 3 ) ( 1 , 1 , 2 ) (x_1,x_2,x_3)(1,1,2) (x1,x2,x3)(1,1,2) ( x 1 , x 2 , x 3 ) ( 1 , 2 , 1 ) (x_1,x_2,x_3)(1,2,1) (x1,x2,x3)(1,2,1) ( x 1 , x 2 , x 3 ) ( 2 , 1 , 1 ) (x_1,x_2,x_3)(2,1,1) (x1,x2,x3)(2,1,1)
如何解决这个问题呢
注意到我们总共有 k 3 k3 k3 个盒子相当于我们有 k − 1 2 k-12 k−12 块板子然后把这两块板子放到不同的间隔方案数。
对于板子我们有 k − 1 k-1 k−1 块对于间隔我们有 n − 1 n-1 n−1 个位置。
因此就是求 ∗ ∗ C n − 1 k − 1 **C_{n-1}^{k-1} ∗∗Cn−1k−1 的方案数** 扩展 与前面不同我们需要求在 x i 0 x_i0 xi0 的条件下求 x 1 x 2 x 3 . . . x k n x_1x_2x_3...x_kn x1x2x3...xkn 的方程解的组数 假设 y i x i 1 y_ix_i1 yixi1 那么 y 1 y 2 y 3 . . . y k n k m y_1y_2y_3...y_knkm y1y2y3...yknkm
因此就可以转换为求 C m − 1 k − 1 C n k − 1 k − 1 C_{m-1}^{k-1} C_{nk-1}^{k-1} Cm−1k−1Cnk−1k−1 的方法数 我们需要求在 x i a i 0 , ∑ 1 n a i p x_ia_i0, \sum_{1}^{n}a_ip xiai0,∑1naip 的条件下求 x 1 x 2 x 3 . . . x k n x_1x_2x_3...x_kn x1x2x3...xkn 的方程解的组数 假设 y i x i − a i 1 y_ix_i-a_i1 yixi−ai1那么 y 1 y 2 y 3 . . . y k n − ∑ 1 k a i k m y_1y_2y_3...y_kn-\sum_{1}^{k}a_ikm y1y2y3...ykn−∑1kaikm
因此就可以转换为求 C m − 1 k − 1 C n − ∑ i 1 k a i k k − 1 C_{m-1}^{k-1}C_{n-\sum_{i1}^{k}a_ik}^{k-1} Cm−1k−1Cn−∑i1kaikk−1 的方案数 例题
方程的解 - 洛谷
首先求出 x x m o d 1000 x^x mod\space 1000 xxmod 1000 的值作为 n n n然后直接求对应的方案数 C n − 1 k − 1 C_{n-1}^{k-1} Cn−1k−1对于如何处理这个组合数我们使用求组合数的递推的方法其中我们需要用到高精度加法来处理。
#includebits/stdc.h
#if 1#define int long long
#endifconst int N150,p1000;
int n,k,x;
int dp[1001][101][N10];
int qpow(int a,int b,int p){int ans1;while (b){if (b1){ansans*a%p;}aa*a%p;b1;}return ans;
}
void add(int ans[],int A[],int B[]){for (int i0;iN;i){ans[i]A[i]B[i];ans[i1]ans[i]/10;ans[i]%10;}
}
void solve(int nn,int mm){//求组合数: C(1000,100)for (int i0;inn;i){for (int j0;ji jmm;j){if (j0){dp[i][j][0]1;}else{//高精度加法add(dp[i][j],dp[i-1][j],dp[i-1][j-1]);}}}
}
signed main(){std::cinkx;nqpow(x,x,p);//a1a2a3...akn//正整数解组数: 满足ai1solve(n-1,k-1);int iN-1;//跳过前导0while (dp[n-1][k-1][i]0){i--;}while (i0){std::coutdp[n-1][k-1][i--];}return 0;
}
