Guest User

Untitled

a guest
Jul 5th, 2019
302
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. typedef long double ld;
  5. typedef long long ll;
  6. const int mod = 998244353;
  7.  
  8. int sum(int a, int b) {
  9. int s = a + b;
  10. if (s >= mod) s -= mod;
  11. return s;
  12. }
  13.  
  14. int sub(int a, int b) {
  15. int s = a - b;
  16. if (s < 0) s += mod;
  17. return s;
  18. }
  19.  
  20. int mult(int a, int b) {
  21. return (1LL * a * b) % mod;
  22. }
  23.  
  24. const int maxN = (int)1e6 + 100;
  25. int a[maxN];
  26. int k;
  27. int fact[maxN];
  28. int inv[maxN];
  29. int invfact[maxN];
  30. int num[maxN];
  31.  
  32. int cnk(int a, int b) {
  33. if (a < b) return 0;
  34. return mult(fact[a], mult(invfact[b], invfact[a - b]));
  35. }
  36.  
  37. void init() {
  38. fact[0] = invfact[0] = fact[1] = invfact[1] = inv[1] = 1;
  39. for (int i = 2; i < maxN; i++) {
  40. fact[i] = mult(fact[i - 1], i);
  41. inv[i] = mult(inv[mod % i], mod - mod / i);
  42. invfact[i] = mult(invfact[i - 1], inv[i]);
  43. }
  44. }
  45.  
  46. int add_val[maxN];
  47.  
  48. int main() {
  49. ios_base::sync_with_stdio(false);
  50. cin.tie(nullptr);
  51. //freopen("input.txt", "r", stdin);
  52. init();
  53. cin >> k;
  54. int S = 0;
  55. int S_res = 0;
  56. for (int i = 0; i < k; i++) {
  57. cin >> a[i];
  58. S += a[i];
  59. int res = a[i] % k;
  60. S_res += res;
  61. add_val[res + 1] += k;
  62. }
  63. for (int i = 0; i < k; i++) {
  64. num[a[i]]++;
  65. }
  66. for (int i = 1; i <= k; i++) num[i] += num[i - 1];
  67. bool fnd = false;
  68. int ans = 0;
  69. for (int moves = 1; moves < k; moves++) {
  70. if (num[moves - 1] >= moves + 1) {
  71. fnd = true;
  72. break;
  73. }
  74. int vals = moves - num[moves - 1];
  75. ans = sum(ans, cnk(vals + k - 1, vals));
  76. }
  77. if (fnd) {
  78. cout << sum(ans, 1);
  79. return 0;
  80. }
  81. int total = 0;
  82. for (int res = 0; res < k; res++) {
  83. if (res > 0) add_val[res] += add_val[res - 1];
  84. int have = (S - S_res - add_val[res] + res * k) / k;
  85. total = sum(total, cnk(have + k - 1, k - 1));
  86. }
  87. cout << total;
  88. return 0;
  89. }
RAW Paste Data