#1187856 (C++23(gcc16)) No.3762 Glowing Utility Pole

• 問題: No.3762 Glowing Utility Pole
• ユーザー: ei1333333
• 提出日時: 2026-09-19 01:36:40
• 言語: C++23(gcc16) (gcc 16.2.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 607 ms / 2,000 ms
• コード長: 3,607 bytes
• コンパイル時間: 2,583 ms
• コンパイル使用メモリ: 372,128 KB
• 実行使用メモリ: 25,600 KB
• 最終ジャッジ日時: 2026-10-09 20:50:43
• 合計ジャッジ時間: 8,213 ms
• ジャッジサーバーID （参考情報）: judge5_1 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

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

using namespace std;

using mint = atcoder::modint998244353;

template <typename T>
struct Enumeration {
private:
  static std::vector<T> _fact, _finv, _inv;

  inline static void expand(std::size_t sz) {
    if (_fact.size() < sz + 1) {
      int pre_sz = std::max(1, (int)_fact.size());
      _fact.resize(sz + 1, T(1));
      _finv.resize(sz + 1, T(1));
      _inv.resize(sz + 1, T(1));
      for (int i = pre_sz; i <= (int)sz; i++) {
        _fact[i] = _fact[i - 1] * T(i);
      }
      _finv[sz] = T(1) / _fact[sz];
      for (int i = (int)sz - 1; i >= pre_sz; i--) {
        _finv[i] = _finv[i + 1] * T(i + 1);
      }
      for (int i = pre_sz; i <= (int)sz; i++) {
        _inv[i] = _finv[i] * _fact[i - 1];
      }
    }
  }

public:
  explicit Enumeration(std::size_t sz = 0) { expand(sz); }

  static inline T fact(int k) {
    expand(k);
    return _fact[k];
  }

  static inline T finv(int k) {
    expand(k);
    return _finv[k];
  }

  static inline T inv(int k) {
    expand(k);
    return _inv[k];
  }

  static T P(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(n - r);
  }

  static T C(int p, int q) {
    if (q < 0 || p < q) return 0;
    return fact(p) * finv(q) * finv(p - q);
  }

  static T H(int n, int r) {
    if (n < 0 || r < 0) return 0;
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};

template <typename T>
std::vector<T> Enumeration<T>::_fact = std::vector<T>();
template <typename T>
std::vector<T> Enumeration<T>::_finv = std::vector<T>();
template <typename T>
std::vector<T> Enumeration<T>::_inv = std::vector<T>();

using E = Enumeration< mint >;

int main() {
  int N, M;
  cin >> N >> M;

  vector<int> C(N);
  for (auto& x : C) {
    cin >> x;
  }

  vector<int> P(N + 1);
  for (int i = 0; i < N; i++) {
    P[i + 1] = P[i] + (C[i] == 0);
  }

  const int T = P[N];

  vector inclusion(M + 1, vector<mint>(M + 1));

  for (int k = 0; k <= M; k++) {
    for (int j = 0; j <= k; j++) {
      inclusion[k][j] = E::C(k, j);
      if (j & 1) {
        inclusion[k][j] = -inclusion[k][j];
      }
    }
  }

  vector prefix_weight(M, vector<mint>(N + 1));
  for (int j = 0; j < M; j++) {
    const mint ratio = mint(M) / mint(M - j);
    mint weight = 1;
    for (int l = 0; l < N; l++) {
      prefix_weight[j][l + 1] = prefix_weight[j][l] + weight;
      if (C[l] == 0) {
        weight *= ratio;
      }
    }
  }

  vector<mint> right_weight(M, 1);
  vector<int> recent;
  int last_zero = -1;
  mint ans = 0;
  for (int r = 1; r <= N; r++) {
    if (const int p = r - 1; C[p] == 0) {
      for (int j = 0; j < M; j++) {
        right_weight[j] *= mint(M - j) / mint(M);
      }
      last_zero = p;
    } else {
      for (int i = 0; i < (int)recent.size(); i++) {
        if (C[recent[i]] == C[p]) {
          recent.erase(recent.begin() + i);
          break;
        }
      }
      recent.push_back(p);
    }
    const int K = (int) recent.size();
    for (int i = K; i >= 0; i--) {
      const int low = i > 0 ? recent[i - 1] + 1 : 0;
      const int high = i < K ? recent[i] + 1 : r;
      if (low >= high) continue;
      const int d = K - i;
      const int missing = M - d;
      mint f = 0;
      for (int j = 0; j <= missing && j < M; j++) {
        f += inclusion[missing][j] * right_weight[j] * (prefix_weight[j][high] - prefix_weight[j][low]);
      }
      if (missing == M) {
        const int begin = max(low, last_zero + 1);
        f += inclusion[M][M] * max(0, high - begin);
      }
      ans += f;
    }
  }
  ans *= mint(M).pow(T);
  cout << ans.val() << endl;
}