题目大意
给定 $n$ 个整数 $ a_1,a_2, \cdots ,a_n $ 作为上界，再给定一个整数 $m$，请问方程
$x_1 + x_2 + \cdots + x_n = m $
有多少种不同的整数解且满足$\ 1\leq x_i\leq a_i$。由于解的数量可能很大，输出答案模$\ 1,000,000,007\ $的余数。
算法思路
假设不定方程无上限限制
对于不定方程中变量 $x$ 我们可以想象它是一个盒子，$x = i$ 代表盒子里有 $i$ 个球。问题相当于你有 $m$ 个球要分给 $n$ 个盒子，不允许某个盒子是空的，方案数量有多少。我们可以使用插板法。插板法就是在 $n$ 个元素间的 $n-1$ 个空中插入若干个 $b$ 个板，可以把n个元素分成 $b+1$ 组的方法。$m$ 个球要分给 $n$ 个盒子则答案为组合数 $C_{m-1}^{n-1}$，即在 $m-1$ 个位置选 $n-1$ 个位置插入隔板的组合数。
稍微扩展一下，有些时候允许某个盒子是空的，直接使用插板法并不可以。
观察方程 $ x_1+x_2+ ... +x_n = m $
可以变为$ (x_1+1)+(x_2+1)+ ... +(x_n+1) = m+n $进一步用 $y_i$ 替换 $x_i+1$ ，得到 $y_1+y_2+ ... +y_n = m+n$
每个 $y_i$ 的正整数解对应一个 $x_i$ 的非负整数解。 增加 待分配的球后，再进行插板法即可，解数量为 $C_{m-1+n}^{n-1}$。
再扩展一下，有些时候要求任意盒子里至少有 $i$ 个球，相当于给所有盒子先预置 $i$ 个球，减少待分配的球后，再进行插板法即可，解数量为 $C_{m-1-i*n}^{n-1}$。
我们可以发现，无上限限制时，无论下限是增加还是减少，我们都可以使用插板法组合数直接求出问题的答案。
方程有上限限制
合法的方案数 = 全部方案数 - 非法方案数
$\left|\bigcap_{i=1}^{n}S_i\right|=|U|-\left|\bigcup_{i=1}^n\overline{S_i}\right|$
对于本题即是 满足上下限制条件解的数量 = 满足下限解的数量 - 不满足上限解的数量。满足下限解的数量我们可以使用插板法之前求出来，接下来我们重点去求不满足上限解的数量即可。到这一步我们就需要容斥原理来帮忙了。
容斥原理
设 $U$ 中元素有 $n$ 种不同的属性，而第 $i$ 种属性称为 $X_i$，拥有属性 $X_i$ 的 元素构成集合$ S_i$，那么
$\begin{aligned}\left|\bigcup_{i=1}^{n}S_i\right|=&\sum_{i}|S_i|-\sum_{i<j}|S_i\cap S_j|+\sum_{i<j<k}|S_i\cap S_j\cap S_k|-\cdots\\&+(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^{m}S_{w_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap S_n|\end{aligned}$
$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^mS_{w_i}\right|$
可以使用数学归纳法和组合数来证明，感兴趣读者可自行查阅资料。
对于本题 $\left|S_i\right|$ 是满足 $x_i$ 上下限制解的数量，$\left|\overline{S_i}\right|$ 是 $x_i \ge a_i+1$解的数量，注意下限问题我们前面讲过了，可以用组合数直接求出。我们要求所有非法解的数量，即$\left|\bigcup_{i=1}^{n}\overline{S_i}\right|$。
根据容斥原理:
$\left|\bigcup_{i=1}^{n}\overline{S_i}\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{w_i<w_{i+1} }\left|\bigcap_{i=1}^m\overline{S_{w_i}}\right|$
源代码分享
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
ll a[25], n, m;
ll f[25] = {1}, rvf[25];
ll rv(ll x){//（快速幂）费马小定理求乘法逆元
// x ^ (MOD - 2)
ll res = 1;
for(ll y = MOD - 2; y; y >>= 1){
if(y % 2) (res *= x) %= MOD;
(x *= x) %= MOD;
}
return res;
}
ll C(ll x, ll y){ //乘法逆元计算组合数
if(x < y) return 0;
ll res = 1;
for(ll i = 1; i <= y; i++) (res *= x--) %= MOD;
(res *= rvf[y]) %= MOD;
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) f[i] = f[i - 1] * i % MOD, rvf[i] = rv(f[i]);
if(n == 1){ cout << (a[1] >= m); return 0; }
ll ans = C(m - 1, n - 1);//隔板法，计算无上限制的解的数量。
for(ll k = 1; k < (1 << n); k++){//二进制枚举
ll cnt = 0, sum = 0;
for(ll p = k, i = 1; p; p >>= 1, i++){ //若二进制第i位为1，让x_i值大于a[i]。
if(p & 1){
cnt++;
sum += a[i];
}
}
ll res = C(m - sum - 1, n - 1); // 非法方案数，把sum个球现放入选定盒子里，再进行插板法，这样选定盒子肯定会超过其上限。
// cout << m - sum - 1 << ' ' << res << endl;
if(cnt % 2) ans -= res; //容斥原理 - 奇数个不满足
else ans += res; // + 偶数个不满足
}
cout << (ans % MOD + MOD) % MOD;
return 0;
}
评论 (0)