Luckyleaves's Blog

stay hungry，stay foolish greedy and lucky

CF451E Devu and Flowers

Posted on Edited on

MlKE永远的神。

题目链接

题目描述

Devu 有 $n$ 个花瓶，第 $i$ 个花瓶里有 $f_i$ 朵花。他现在要选择 $s$ 朵花。

你需要求出有多少种方案。两种方案不同当且仅当两种方案中至少有一个花瓶选择花的数量不同。

答案对 $10^9+7$ 取模。

$1\le n\le 20,0\le f_i\le 10^{12},0\le s\le 10^{14}$

Solution

首先考虑$ \forall s \le f_i $的情况，很显然这就是多重集的组合数，答案就是$C_{n+s-1}^{s}$，那么现在思考如何消去$s > f_i$ 的影响，我们设：有$x$个花瓶满足这些花瓶取的花至少为$f_i+1$ 的方案数为$num_x$，其中剩下的花在所有花瓶中任意取，很明显，这就可能使有$>x$个花瓶超出自身限制，观察范围，发现$n$小的离谱，那么我们考虑容斥解决误差，枚举每个花瓶是否溢出，然后答案就是：$num_0-num_1+num_2…+(-1)^nnum_n$。

最后在观察式子，发现没有必要将每个$num$都算出来，枚举时减去$x$为奇数的答案，加上$x$为偶数的答案即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define int long long
using namespace std;
template <class T>
inline void read(T &res)
{
    res = 0; bool flag = 0;
    char c = getchar();
    while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();}
    while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar();
    if(flag) res = -res;
}
template <class T, class ...Arg>
inline void read(T &res, Arg &...com){ read(res), read(com...);}
template <class T>
void out(T res)
{
    if(res > 9) out(res / 10);
    putchar(res % 10 + '0');
}
template <class T>
inline void write(T res)
{
    if(res < 0) putchar('-'), res = -res;
    out(res), putchar('\n');
}
const int N = 20, M = (1 << N) + 5, mod = 1e9 + 7;
int n, m;
LL a[N + 5];
int ans;
inline int qpow(int x, int k)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = 1ll * x * res % mod;
        x = 1ll * x * x % mod;
        k >>= 1;
    }
    return res;
}
inline int C(LL x, LL y)
{
    if(x > y) return 0;
    x = min(y - x, x);
    int res = 1, a = 1, b = 1;
    for(int i = 1;i <= x;i ++) a = 1ll * a * (y - i + 1) % mod, b = 1ll * b * i % mod; 
    res = 1ll * res * a % mod * qpow(b, mod - 2) % mod;
    return res;
}
inline int lucas(LL x, LL y)
{
    if(x < mod && y < mod) return C(x, y);
    return 1ll * lucas(x / mod, y / mod) * C(x % mod, y % mod) % mod;
}
signed main()
{
    read(n, m);
    for(int i = 1;i <= n;i ++) read(a[i]);
    for(int i = 0, cnt, sum;i < (1 << n);i ++)
    {
        cnt = sum = 0;
        for(int j = 1;j <= n;j ++)
            if((i >> j - 1) & 1) cnt ++, sum += a[j] + 1;
        if(sum > n + m - 1) continue;
        if(cnt & 1) ans = (ans - lucas(n - 1, m + n - sum - 1)) % mod;
        else ans = (ans + lucas(n - 1, n + m - sum - 1)) % mod;
    }
    write((ans + mod) % mod);
    return 0;
}