Submission #47081712

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/convolution>
#include <atcoder/modint>
const int MOD = 998244353;
using mint = atcoder::static_modint<MOD>;
using namespace std;
#define rep(i, a, n) for (int i = a; i < (int)(n); i++)
int read() { int r; scanf("%d", &r); return r; }

int main() {
  int n = read();
  int m = read();
  int k = read();
  int l = read();
  vector<mint> res(2 * m + 2, 0);
  rep(i, 0, k) {
    int off = read();
    res[off]++;
    res[2 * m + 2 - off]--;
  }
  // res * ((1+x+x^2)/x)^{n-1} mod (x^{2m+2}-1)
  vector<mint> v(3, 1);  // 1+x+x^2
  auto mul = [&](const vector<mint>& a, const vector<mint>& b) {  // a * b  % (x^{2m+2} - 1)
    vector<mint> ret = atcoder::convolution(a, b);
    while ((int)ret.size() > 2 * m + 2) {
      ret[(ret.size() - 1) % (2 * m + 2)] += ret.back();
      ret.pop_back();
    }
    return ret;
  };
  int p = n - 1;
  while (p) { // * (1+x+x^2)^{n-1}
    if (p & 1) res = mul(res, v);
    v = mul(v, v);
    p /= 2;
  }
  // assert(res[(n - 1) % (2 * m + 2)].val() == 0);
  mint ans = 0;
  rep(i, 0, l) ans += res[(read() + (n - 1)) % (2 * m + 2)]; // off -> (off+(n-1)) % (2m+2)
  printf("%d\n", ans.val());
  return 0;
}

Submission Info

Compile Error

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

Judge Result