隔板法（求解的组数）

隔板法（求解的组数）

文章首发于我的个人博客：欢迎大佬们来逛逛

隔板法

隔板法能够解决的问题：

• 求线性不定方程的解的组数
• 求相同元素分组的方案数

---

给我们 $n$ 个球， $k$ 个盒子，要求把这些球放进这些盒子中，一共有多少种不同的放的方案数？

例如：

$n=4，k=3$ ，方案如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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_1+x_2+x_3+...+x_k=n$ 的方程解的组数

即在这个问题中，方程的解的组数就是：

1. $(x_1,x_2,x_3)=(1,1,2)$
2. $(x_1,x_2,x_3)=(1,2,1)$
3. $(x_1,x_2,x_3)=(2,1,1)$

如何解决这个问题呢？

注意到我们总共有 $k=3$ 个盒子，相当于我们有 $k-1=2$ 块板子，然后把这两块板子放到不同的间隔方案数。

对于板子，我们有 $k-1$ 块；对于间隔，我们有 $n-1$ 个位置。

因此就是求：$\ast \ast C_{n-1}^{k-1}$ 的方案数**

---

扩展

与前面不同，我们需要求在 $x_i>=0$ 的条件下，求 $x_1+x_2+x_3+...+x_k=n$ 的方程解的组数

假设 $y_i=x_i+1$ ，那么 $y_1+y_2+y_3+...+y_k=n+k=m$

因此就可以转换为求： $C_{m-1}^{k-1}=C_{n+k-1}^{k-1}$ 的方法数

---

我们需要求在 $x_i>=a_i>=0,{\sum }_1^n{a}_i<=p$ 的条件下，求 $x_1+x_2+x_3+...+x_k=n$ 的方程解的组数

假设 $y_i=x_i-a_i+1$，那么 $y_1+y_2+y_3+...+y_k=n-{\sum }_1^k{a}_i+k=m$

因此就可以转换为求：$C_{m-1}^{k-1}=C_{n-{\sum }_{i=1}^k{a}_i+k}^{k-1}$ 的方案数

---

例题

方程的解 - 洛谷

1. 首先求出 $x^{x}mod1000$ 的值，作为 $n$
2. 然后直接求对应的方案数：$C_{n-1}^{k-1}$
3. 对于如何处理这个组合数，我们使用求组合数的递推的方法，其中我们需要用到高精度加法来处理。

#include<bits/stdc++.h>
#if 1#define int long long
#endifconst int N=150,p=1000;
int n,k,x;
int dp[1001][101][N+10]; 
int qpow(int a,int b,int p){int ans=1;while (b){if (b&1){ans=ans*a%p;}a=a*a%p;b>>=1;}return ans;
}
void add(int ans[],int A[],int B[]){for (int i=0;i<=N;i++){ans[i]+=A[i]+B[i];ans[i+1]+=ans[i]/10;ans[i]%=10;}
}
void solve(int nn,int mm){//求组合数: C(1000,100)for (int i=0;i<=nn;i++){for (int j=0;j<=i && j<=mm;j++){if (j==0){dp[i][j][0]=1;}else{//高精度加法add(dp[i][j],dp[i-1][j],dp[i-1][j-1]);}}}
}
signed main(){std::cin>>k>>x;n=qpow(x,x,p);//a1+a2+a3...+ak=n//正整数解组数: 满足ai>=1solve(n-1,k-1);int i=N-1;//跳过前导0while (dp[n-1][k-1][i]==0){i--;}while (i>=0){std::cout<<dp[n-1][k-1][i--];}return 0;
}