結果

問題 No.3247 Multiplication 8 2
ユーザー Kude
提出日時 2025-08-23 00:51:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 525 ms / 4,000 ms
コード長 2,316 bytes
コンパイル時間 3,912 ms
コンパイル使用メモリ 314,492 KB
実行使用メモリ 29,592 KB
最終ジャッジ日時 2025-08-23 00:51:25
合計ジャッジ時間 16,003 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using mint = modint998244353;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, K;
  cin >> n >> K;
  VI a(n);
  rep(i, n) cin >> a[i];
  {
    int cnt = count(all(a), 2) + count(all(a), -2);
    if (cnt == 0 || cnt % 3) {
      cout << 0 << '\n';
      return 0;
    }
  }
  vector<mint> dpf(n + 1), dpb(n + 1);
  rep(_, 2) {
    int v[]{1, 2, 4, 8, -1, -2, -4, -8};
    dpf[0] = 1;
    mint d[8];
    d[0] = 1;
    rep(i, n) {
      mint nd[8];
      rep(j, 8) {
        int nx = v[j] * a[i];
        if (nx == 8) dpf[i+1] += d[j], nd[0] += d[j];
        if (int nj = find(all(v), nx) - v; nj != 8) nd[nj] += d[j];
      }
      swap(d, nd);
    }
    reverse(all(a));
    swap(dpf, dpb);
  }
  reverse(all(dpb));
  mint ans;
  int cnt = 0;
  vector<char> sgn(n + 1);
  rep(i, n) sgn[i+1] = sgn[i] ^ (a[i] < 0);
  rep(i, n) {
    cnt += abs(a[i]) == 2;
    if (cnt == 3) {
      int r1 = i + 1;
      int r2 = r1;
      while (r2 < n && abs(a[r2]) == 1) r2++;
      int l1 = i + 1;
      while (cnt) {
        l1--;
        cnt -= abs(a[l1]) == 2;
      }
      int l2 = l1;
      while (l2 && abs(a[l2-1]) == 1) l2--;
      // [l2,l1] * [r1,r2]
      vector<mint> fl(l1 - l2 + 1), fr(r2 - r1 + 1);
      for (int i = l2; i <= l1; i++) if (sgn[i] == 0) fl[l1-i] = dpf[i];
      for (int i = r1; i <= r2; i++) if (sgn[i] == 0) fr[i-r1] = dpb[i];
      auto f = convolution(fl, fr);
      // k = l1-i + j-r1 = j-i + l1 - r1
      for (int k = 0; k < ssize(f); k++) {
        ans += mint(k - l1 + r1).pow(K) * f[k];
      }
    }
  }
  cout << ans.val() << '\n';
}
0