不定方程解的个数、容斥原理、状压、组合计数

题意：需要从N个盒子中总共取出M枝花，每个盒子中的花是相同的，问有多少种取法。

假设每个盒子中的花有无限，记从第i个盒子中取出x[i]枝花，则有：
$x[1] + x[2] + … + x[N] = M$，令$y[i] = x[i] + 1$，

=>$[1] + y[2] + .. + y[N] = M + N$

=>方案数：$C_{N+M-1}^{N-1}$

回到原问题，直接从正面求不好求，那就用补集的思想：合法方案数=总方案数-非法方案数！

总方案数：$C_{N+M-1}^{N-1}$；

非法方案：至少存在从一个从盒子中取花的数量大于盒子中存在的花的数量的取法
记第i个盒子非法的集合为S[i]，则所有非法方案数为$|S[1]∩S[2]∩…∩S[N]|$

合法方案数= $C_{N+M-1}^{N-1} + (-1)^{k-1}\sum_{1<=i<=N}{C_{N+M-2-A[i]}^{N-1}} + (-1)^{k-1} \sum_{1<=i<j<=N}{C_{N+M-3-A[i]-A[j]}^{N-1}} + … +$ ,
(其中k是集合个数)

如何方便地去计算非法方案？
容斥原理中项的个数是$2^N$个，对应这N个条件的选或者不选，因此可以把每一种情况看成一个二进制表达式，
1代表选，0代表不选；1的个数是奇数为-，1的个数为偶数为＋。

因为N很小，所以C可以直接用定义计算，因为模的是质数，所以除的数可以用快速幂算出逆元转换成乘

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 20 , mod = 1e9 + 7;

LL A[N];
int down = 1;

int qmi(int a, int k)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;

    return (LL)up * down % mod; // 费马小定理
}



int main()
{
    LL n , m;
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++)    cin >> A[i];

    for(int i = 1 ; i <= n - 1 ; i++) down = (LL)down * i % mod;
    down = qmi(down , mod - 2);

    int res = 0;
    for(int i = 0 ; i < 1 << n ; i++)
    {
        LL a = m + n - 1 , b = n - 1;
        int sign = 1;
        for(int j = 0 ; j < n ; j++)
        {
            if(i >> j & 1)
            {
                sign *= -1;
                a -= 1 + A[j];
            }
        }

        res = (res + C(a , b) * sign) % mod;
    }

    cout << (res + mod) % mod << endl;
    return 0;
}