AtCoder ARC134C – The Majority – 简略题解与思路重现

AtCoder ARC 134 C – The Majority

如此ruzhi的一道题目竟花去两小时有余,比赛结束也没写出来,实在惭愧。

拿到题目,很快想到一种DP:令f(i,j,k)f(i, j, k)表示“考虑到第ii个盒子,第11种小球用去jj个,第2,3,,n2, 3, \dots, n种小球用去kk个”的方案数。容易转移

然后发现aia_i10910^9级别。同时题目告诉我们,相同类别小球无法区分,所以要是上述做法正确,为什么要分别给出a2,a3,a_2, a_3, \dots呢?如何在转移时确保每一种小球的使用次数正确?立刻想到正解O(ai)\mathrm{O}(a_i)基本无关。

但好巧不巧,上下眼皮开始打架了,也没有努力保持专注。于是就在这个显然毫无可能性的做法上耗掉整整一小时。期间考虑了和DP很多办法,例如将问题简化(若是只有2,3,2, 3, \dots种物品,2,3,2, 3, \dots个盒子该怎么做),或者似乎没有什么用处的转化成判定性问题(什么情况下答案一定为00?),均无疾而终。

再过一会,发现一个性质:假如a1=i=2nai+ka_1=\sum\limits_{i=2}^{n}a_i+k,那么就代表“每个盒子至少放了1111类小球,且每多在某个盒子中放置112,3,,n2, 3, \dots, n类小球,该盒子中必定多放1111类小球”。这时,如果只考虑填放第2,3,,n2, 3, \dots, n种小球的方案,任意一种合法的方案均可以对应一种唯一一种合法的放置11类小球的方案。具体地,考虑在第ii个盒子中放置了xix_i个非11类小球。则我们必须——且恰好——要放xi+1x_i+111类小球,最终刚好放完。

若是a1<i=2nai+ka_1<\sum\limits_{i=2}^{n}a_i+k,则显然无解。如果a1>i=2nai+ka_1>\sum\limits_{i=2}^{n}a_i+k,那么剩下的小球怎么放呢?记g=a1i=2nai+kg=a_1-\sum\limits_{i=2}^{n}a_i+k,则等价于“将gg个同类物品放入kk组中,可以空放”。这就转化为经典的插板法排列组合问题。答案应为(g+k1k1)\dbinom{g+k-1}{k-1}

有一个问题:gg的范围是如此之大(10910^9),怎么快速计算呢?注意到kk很小(200200),所以我们化(xy)\dbinom{x}{y}x!y!(xy)!=i=xy+1xi×inv(y!)\dfrac{x!}{y!(x-y)!}=\prod\limits_{i=x-y+1}^{x}i \times \text{inv}(y!),暴力计算连乘积,预处理(如果懒,甚至不用预处理)乘法逆元即可。

同理,我们可以对每一个ai,i[2,n]a_i, i\in [2, n]计算出其放置方案,对于aia_i(ai+k1k1)\dbinom{a_i+k-1}{k-1},最终由乘法原理可知,最终答案是其连乘积。时间复杂度O(nk)\mathrm{O}(nk)

Submission #28882453

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
  43. 43
  44. 44
  45. 45
  46. 46
  47. 47
  48. 48
  49. 49
  50. 50
  51. 51
  52. 52
  53. 53
  54. 54
  55. 55
  56. 56
  57. 57
  58. 58
  59. 59
  60. 60
  61. 61
  62. 62
  63. 63
  64. 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; }
  • 2022年1月30日