【組合數學 && 容斥 && C(n, m)%p && 逆元 && m 個大于等于 0 的數組成 k 的方案數】CodeForces - 451E Devu and Flowers

Step1 Problem:

給你 n 個盒子，每個盒子裡面有 f[i] 朵花，不同盒子花不一樣，同一個盒子花一樣，求從這 n 個盒子選出 s 朵花得方案數

資料範圍：

1 <= n <= 20, 0 <= s <= 1e14, 0 <= fi <= 1e12.

Step2 Ideas:

逆元學習地方

a * x ≡ 1(mod p)。

因為p是素數，是以我們求逆元可以用費馬小定理 和 歐拉定理

a^(p-1) ≡ 1(mod p) -> a*a^(p-2) ≡ 1(mod p)。是以a^(-1) = a^(p-2)

還有一種通用的求逆元方法，适合所有情況。公式如下

現在我們來證明它，已知，證明步驟如下

Lucas定理

那麼得到

這樣然後分别求，采用逆元計算即可。

這題學習部落格

從 n 個盒子選花，有的盒子可以不選，組成 s 的方案數 可以轉換為：

s 個球是無标志的，n 個盒子是由差別的，取 s 個球放進盒子，每個盒子允許多于一個球。

相當于有 s+n-1 個物品擺放着，我們從中選取 n-1 個當作隔闆，被隔闆隔開的物品就相當于每個盒子的球的數量。

從 n 個盒子選花，有的盒子可以不選，組成 s 的方案數 = C(s+n-1, n-1)；

這題有 f[i] 的限制，這樣計數的話某些花會超出其個數，我們可以進行容斥：

比如确定 i 超出個數其它不确定的方案 C(sum-(f[i]+1)+n-1,n-1)

因為 n <= 20, 是以我們可以二進制枚舉确定哪些 i 超出容斥

是以 ans = 超0 - 超1 + 超2 - 超3 …

Lucas 适用于 n 和 m 很大，但是 MOD 不是特别大

這題可以不用 Lucas, 因為 n 很小

Step3 Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9+7;
ll f[25];
ll Pow(ll a, ll n)//快速幂
{
    ll sum = 1;
    while(n)
    {
        if(n&1) sum = sum*a % MOD;
        a = a*a % MOD;
        n >>= 1;
    }
    return sum;
}
ll C(ll n, ll m)//c(n,m)
{
    ll a = 1, b = 1;
    if(m > n) return 0;
    if(m > n/2) {
        m = n-m;
    }
    if(m == 0) return 1;
    for(ll i = 1; i <= m; i++)
    {
        a = a*(n+i-m) % MOD;
        b = b*i % MOD;
    }
    return (a*Pow(b, MOD-2)%MOD)%MOD;//a*b^(-1)%MOD
}
ll Lucas(ll n, ll m)//Lucas定理 m <= n
{
    if(!m) return 1;
    return C(n%MOD, m%MOD) * Lucas(n/MOD, m/MOD) % MOD;
}
int main()
{
    int n;
    ll s;
    scanf("%lld %lld", &n, &s);
    for(int i = 0; i < n; i++)
        scanf("%lld", &f[i]);
    ll ans = 0;
    for(int k = 0; k < (1<<n); k++)
    {
        ll sum = s; int flag = 0;
        for(int i = 0; i < n; i++)
        {
            if((1<<i)&k) {
                sum -= f[i]+1;
                flag ^= 1;
            }
        }
        if(sum < 0) continue;
        if(!flag) {
            ans += Lucas(sum+n-1, n-1); ans %= MOD;
        }
        else {
            ans -= Lucas(sum+n-1, n-1); ans = (ans%MOD+MOD)%MOD;
        }
    }
    printf("%lld\n", ans);
    return 0;
}