AtCoder ARC 134 C – The Majority
如此ruzhi的一道题目竟花去两小时有余,比赛结束也没写出来,实在惭愧。
拿到题目,很快想到一种DP:令表示“考虑到第个盒子,第种小球用去个,第种小球用去个”的方案数。容易转移。
然后发现是级别。同时题目告诉我们,相同类别小球无法区分,所以要是上述做法正确,为什么要分别给出呢?如何在转移时确保每一种小球的使用次数正确?立刻想到正解与基本无关。
但好巧不巧,上下眼皮开始打架了,也没有努力保持专注。于是就在这个显然毫无可能性的做法上耗掉整整一小时。期间考虑了和DP很多办法,例如将问题简化(若是只有种物品,个盒子该怎么做),或者似乎没有什么用处的转化成判定性问题(什么情况下答案一定为?),均无疾而终。
再过一会,发现一个性质:假如,那么就代表“每个盒子至少放了个类小球,且每多在某个盒子中放置个类小球,该盒子中必定多放个类小球”。这时,如果只考虑填放第种小球的方案,任意一种合法的方案均可以对应一种唯一一种合法的放置类小球的方案。具体地,考虑在第个盒子中放置了个非类小球。则我们必须——且恰好——要放个类小球,最终刚好放完。
若是,则显然无解。如果,那么剩下的小球怎么放呢?记,则等价于“将个同类物品放入组中,可以空放”。这就转化为经典的插板法排列组合问题。答案应为。
有一个问题:的范围是如此之大(),怎么快速计算呢?注意到很小(),所以我们化为,暴力计算连乘积,预处理(如果懒,甚至不用预处理)乘法逆元即可。
同理,我们可以对每一个计算出其放置方案,对于有,最终由乘法原理可知,最终答案是其连乘积。时间复杂度。
- 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
#include <bits/stdc++.h> using namespace std; template <typename T> inline bool read (T &x) { x = 0; int f = 1; char c = getchar (); for (; c != EOF && !isdigit (c); c = getchar ()) if (c == '-') f = -1; if (c == EOF) return 0; for (; c != EOF && c >= '0' && c <= '9'; c = getchar ()) x = (x<<1) + (x<<3) + (c^48); x *= f; return 1; } template <typename T, typename ...Targs> inline bool read (T &x, Targs& ... args) { return read (x) && read (args...); } template <typename T> void print (T x) { if (x < 0) putchar ('-'), x = -x; if (x >= 10) print (x / 10); putchar (x % 10 + '0'); } #define reint register int #define inl inline #define newl putchar('\n') typedef long long ll; typedef __int128 lll; typedef pair <int, int> pint; const int N = 1e5 + 10, P = 998244353; ll a, b[N], sum, n, k, tmp, ans; int inv[256], finv[256]; inl int C (int x, int y) { if (y > x) return 0; int res = 1; for (int i = x - y + 1; i <= x; ++i) res = 1ll * res * i % P; return 1ll * res * finv[y] % P; } #define proc(x) (((x) % P + P) % P) inl void calc_inv () { inv[1] = 1; for (int i = 2; i <= k; ++i) inv[i] = proc (-(1ll * (P / i) * inv[P % i] % P)); finv[0] = 1; for (int i = 1; i <= k; ++i) finv[i] = finv[i - 1] * 1ll * inv[i] % P; } int main () { /* */ read (n, k, a); for (int i = 2; i <= n; ++i) read (b[i]), sum += b[i]; if (a < sum + k) return puts ("0"), 0; ans = 1; calc_inv (); for (int i = 2; i <= n; ++i) ans = ans * C (b[i] + k - 1, k - 1) % P; ans = ans * C (a - sum - 1, k - 1) % P; print (ans); return 0; }