結果

問題 No.3247 Multiplication 8 2
ユーザー Kude
提出日時 2025-08-23 00:06:04
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 988 ms / 4,000 ms
コード長 2,523 bytes
コンパイル時間 3,912 ms
コンパイル使用メモリ 314,804 KB
実行使用メモリ 32,192 KB
最終ジャッジ日時 2025-08-23 00:06:31
合計ジャッジ時間 26,796 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
  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[2], fr[2];
      rep(i, 2) fl[i].resize(l1 - l2 + 1), fr[i].resize(r2 - r1 + 1);
      bool sgn = 0;
      for (int i = l2; i <= l1; i++) {
        fl[sgn][l1 - i] = dpf[i];
        if (i < l1 && a[i] < 0) sgn ^= 1;
      }
      for (int i = l1; i < r1; i++) if (a[i] < 0) sgn ^= 1;
      for (int i = r1; i <= r2; i++) {
        fr[sgn][i - r1] = dpb[i];
        if (i < r2 && a[i] < 0) sgn ^= 1;
      }
      rep(sgn, 2) {
        auto f = convolution(fl[sgn], fr[sgn]);
        // 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