提出 #35638390

---

ソースコード 拡げる

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
using vm = vector<mint>;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

void fftrow(vector<vm>& a, bool rev = false) { // a[xor][plus]
  // int n = a.size(); // 2的幂次
  int m = a[0].size(); // 2的幂次
  if (rev) { // 对每一行做 ifft
    mint invm = mint{m}.inv();
    for (auto& v : a) {
      atcoder::internal::butterfly_inv(v);
      for (auto& x : v) x *= invm;
    }
  } else { // 对每一行做fft
    for (auto& v : a) atcoder::internal::butterfly(v);
  }
}

void ifftrow(vector<vm>& a){ fftrow(a,true);}

void fwtcol(vector<vm>& a, bool rev = false) { // a[xor][plus]
  int n = a.size(); // 2的幂次
  int m = a[0].size(); // 2的幂次
  mint flag=rev?mint(2).inv():1;
  rep(k,0,m){
    // FWT / IFWT
    for(int l=1;l<n;l*=2){ // len
      for (int s = 0; s < n; s += 2*l) { // start pos
        rep(i,s,s+l){ // [s..s+l) <=> [s+l..s+2l)
          mint T=a[i][k];
          mint U=a[l+i][k];
          a[i][k]   = (T+U)*flag;
          a[l+i][k] = (T-U)*flag;
        }
      }
    }
  }
}

void ifwtcol(vector<vm>&a){fwtcol(a,true);}

pair<int,int> calc(int s, int g, int W) {
  if (g < s) return {0, s - g - 1};
  return {(s - 1) - (W - g), 0};
}

int main() {
  int H=read();
  int W=read();

  int X = 1; // X 为 >=W的2的幂次
  int Y = 1; // Y 为 >=2HW的2的幂次
  while (X < W) X *= 2;
  while (Y < 2 * H * W) Y *= 2;

  auto f=vector(X, vm(Y)); // f[相向差][向左-向右 差]=方案数,如果结果非负, 则 <= H*W, 否则 负 >= H*W, 通过 % Y实现
  rep(s,1,W+1) rep(g,1,W+1) if (s != g){ /// s向左移动, g向右移动
    auto [surreal, grundy] = calc(s, g, W);
    f[grundy][(surreal+Y)%Y] ++;
  }
  fftrow(f);
  fwtcol(f);
  rep(i,0, X) rep(j,0, Y) f[i][j] = f[i][j].pow(H);// A^t = ifft( (fft(A)每项)^t)
  ifwtcol(f);
  ifftrow(f);

  mint ans = 0;
  rep(i,0, X) rep(j,0, Y / 2) if (i > 0 or j > 0) ans += f[i][j];
  printf("%d\n",ans.val());
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘ll read()’:
./Main.cpp:13:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   13 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果