题解 - [Luogu P6078] [CEOI2004] Sweets

发表于 更新于 分类于 ， 本文字数： 446 阅读时长 ≈ 2 分钟

题目链接

原始题面

题目描述

John 得到了 \(n\) 罐糖果。不同的糖果罐，糖果的种类不同 (即同一个糖果罐里的糖果种类是相同的，不同的糖果罐里的糖果的种类是不同的). 第 \(i\) 个糖果罐里有 \(m_{i}\) 个糖果. John 决定吃掉一些糖果，他想吃掉至少 \(a\) 个糖果，但不超过 \(b\) 个。问题是 John 无法确定吃多少个糖果和每种糖果各吃几个。有多少种方法可以做这件事呢？

输入输出格式

输入格式

输入共 \(n+1\) 行：第一行读入 \(n\), \(a\), \(b\). 接下来 \(n\) 行，一行一个数，代表 \(m_{i}\)

输出格式

仅一行，表示 John 能够选择的满足以上条件的吃掉糖果的方法数，答案对 \(2004\) 取模

输入输出样例

输入样例 #1

1
2
3
2 1 3
3
5

输出样例 #1

1
9

说明

数据范围及限制

对于 \(100\%\) 的数据，保证 \(1\leq n \leq 10\), \(0\leq a \leq b \leq 10^7\), \(0 \leq m_{i} \leq 10^6\)

说明

本题译自 Central European Olympiad in Informatics 2004 Day 1 T2 Sweets

解题思路

显然要转成 OGF, 题目即求

\[ \prod_{k=1}^n\sum_{j=0}^{m_k}x^j \]

的 \(x^a\) 到 \(x^b\) 项的系数和

整理一下

\[ \begin{aligned} \prod_{k=1}^n\sum_{j=0}^{m_k}x^j&=\prod_{k=1}^n\frac{1-x^{m_k+1}}{1-x}\\ &=(1-x)^{-n}\prod_{k=1}^n(1-x^{m_k+1})\\ &=\left(\sum_{i=0}^{\infty}\binom{n+i-1}{i}x^i\right)\prod_{k=1}^n(1-x^{m_k+1})\\ \end{aligned} \]

由于

\[ \sum_{i=s-l+1}^s\binom{n+i-1}{i}=\binom{n+s}{n}-\binom{n+s-k}{n} \]

所以直接 DFS 即可

复杂度

\(O(n2^n)\)

代码参考

Show code

Luogu_P6078view raw
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
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _rfor(i, r, l, vals...)                                      \
  for (make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vals; \
       i >= i##end;                                                  \
       --i)
const i64 MOD = 2004;
const i64 FACT[11] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
i64 m_choose_n(i64 m, i64 n) {
  if (n > m) return 0;
  i64 ans = 1;
  _rfor(i, m, m - n + 1) (ans *= i) %= MOD * FACT[n];
  return ans / FACT[n] % MOD;
}
int m[15];
int n, a, b;
i64 dfs(int now, int expm) {
  if (expm > b) return 0;
  if (now > n)
    return (m_choose_n(n + b - expm, n) + MOD -
            m_choose_n(n + a - expm - 1, n)) %
           MOD;
  return (dfs(now + 1, expm) + MOD - dfs(now + 1, expm + m[now] + 1)) % MOD;
}
auto solve() -> void {
  cin >> n >> a >> b;
  _for(i, 1, n) cin >> m[i];
  cout << dfs(1, 0);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  solve();
  return 0;
}