結果

問題 No.2005 Sum of Power Sums
ユーザー KumaTachiRenKumaTachiRen
提出日時 2023-09-29 10:26:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,990 bytes
コンパイル時間 4,932 ms
コンパイル使用メモリ 271,376 KB
実行使用メモリ 21,532 KB
最終ジャッジ日時 2023-09-29 10:27:08
合計ジャッジ時間 11,485 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 117 ms
4,376 KB
testcase_01 AC 121 ms
4,380 KB
testcase_02 AC 156 ms
4,376 KB
testcase_03 AC 117 ms
4,380 KB
testcase_04 AC 120 ms
4,380 KB
testcase_05 AC 116 ms
4,376 KB
testcase_06 AC 118 ms
4,380 KB
testcase_07 AC 124 ms
4,376 KB
testcase_08 AC 120 ms
4,380 KB
testcase_09 AC 120 ms
4,376 KB
testcase_10 AC 132 ms
4,376 KB
testcase_11 AC 137 ms
4,376 KB
testcase_12 AC 212 ms
4,380 KB
testcase_13 AC 220 ms
4,376 KB
testcase_14 AC 441 ms
16,956 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;

struct Fast {
  Fast() {
    std::cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(10);
  }
} fast;

#define all(a) (a).begin(), (a).end()
#define contains(a, x) ((a).find(x) != (a).end())
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b)-1; i >= (a); i--)
#define writejoin(s, a) rep(_i, 0, (a).size()) cout << (a)[_i] << (_i + 1 < (int)(a).size() ? s : "\n");
#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";
#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";
#define yn(b) cout << ((b) ? "yes" : "no") << "\n";

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using mint = modint998244353;
using vm = vector<mint>;

template <typename mint>
class Factorial {
 public:
  Factorial(int max) : n(max) {
    f = vector<mint>(n + 1);
    finv = vector<mint>(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] * i;
    finv[n] = f[n].inv();
    for (int i = n; i > 0; i--) finv[i - 1] = finv[i] * i;
  }
  mint fact(int k) {
    assert(0 <= k && k <= n);
    return f[k];
  }
  mint fact_inv(int k) {
    assert(0 <= k && k <= n);
    return finv[k];
  }
  mint binom(int k, int r) {
    assert(0 <= k && k <= n);
    if (r < 0 || r > k) return 0;
    return f[k] * finv[r] * finv[k - r];
  }
  mint inv(int k) {
    assert(0 < k && k <= n);
    return finv[k] * f[k - 1];
  }

 private:
  int n;
  vector<mint> f, finv;
};

template <typename mint>
mint bostan_mori(vector<mint> a, vector<mint> b, ll n) {
  if (a.size() < b.size()) a.resize(b.size());
  auto c = vector<mint>(b.size());
  while (n) {
    rep(i, 0, b.size()) c[i] = i % 2 == 0 ? b[i] : -b[i];
    auto a1 = convolution(a, c), b1 = convolution(b, c);
    int r = (int)(n % 2);
    for (int i = 0; i < a.size() && i * 2 + r < a1.size(); i++)
      a[i] = a1[i * 2 + r];
    for (int i = 0; i < b.size(); i++) b[i] = b1[i * 2];
    n /= 2;
  }
  return a[0] / b[0];
};

int main() {
  int n;
  ll m;
  cin >> n >> m;
  const int max = 5000;
  vi c(max + 1, 0);
  rep(i, 0, n) {
    int k;
    cin >> k;
    c[k]++;
  }

  vm p{1}, q{1, -1}, f(max + 1, 0);

  for (int k = 1; k <= max; k++) {
    vm newp(k + 1, 0);
    for (int i = 1; i < k; i++) newp[i] += p[i] * i;
    for (int i = k - 1; i >= 0; i--) newp[i + 1] -= newp[i];
    for (int i = 0; i < k; i++) newp[i + 1] += p[i] * k;
    p = newp;
    vm newq(k + 2, 0);
    for (int i = 0; i < k + 1; i++) {
      newq[i] += q[i];
      newq[i + 1] -= q[i];
    }
    q = newq;
    for (int i = max; i > 0; i--) f[i] -= f[i - 1];
    if (c[k] > 0) {
      rep(i, 0, p.size()) f[i] += c[k] * p[i];
    }
  }
  Factorial<mint> fact(n);
  vm r(n + 1, 0);
  rep(i, 0, n + 1) {
    r[i] = fact.binom(n, i);
    if (i & 1) r[i] = -r[i];
  }
  q = convolution(q, r);
  mint ans = bostan_mori<mint>(f, q, m);
  cout << ans.val() << endl;
}
0