結果

問題 No.2237 Xor Sum Hoge
ユーザー KudeKude
提出日時 2023-03-04 03:07:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,401 bytes
コンパイル時間 2,348 ms
コンパイル使用メモリ 219,216 KB
最終ジャッジ日時 2024-11-15 03:34:35
合計ジャッジ時間 2,715 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp: In function '{anonymous}::mint {anonymous}::solve(int, ll, ll)':
main.cpp:56:27: error: 'ceil_pow2' is not a member of '{anonymous}::atcoder::internal'
   56 |   const int z = internal::ceil_pow2((2 * n + 3) * 4), sz = 1 << z;
      |                           ^~~~~~~~~
main.cpp:57:18: error: 'sz' was not declared in this scope; did you mean 'z'?
   57 |   vector<mint> f(sz), g(sz), h(sz);
      |                  ^~
      |                  z
main.cpp: At global scope:
main.cpp:49:6: warning: '{anonymous}::mint {anonymous}::perm(int, int)' defined but not used [-Wunused-function]
   49 | mint perm(int n, int k) {
      |      ^~~~
main.cpp:48:6: warning: '{anonymous}::mint {anonymous}::fact(int)' defined but not used [-Wunused-function]
   48 | mint fact(int n) {return Fact[n];}
      |      ^~~~
main.cpp:44:6: warning: '{anonymous}::mint {anonymous}::icomb(int, int)' defined but not used [-Wunused-function]
   44 | mint icomb(int n, int k) {
      |      ^~~~~

ソースコード

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;

constexpr int FACT_SIZE = 1000000;
mint Fact[FACT_SIZE + 1];
mint iFact[FACT_SIZE + 1];
const auto fact_init = [] {
    Fact[0] = mint::raw(1);
    for(int i = 1; i <= FACT_SIZE; ++i) {
        Fact[i] = Fact[i-1] * i;
    }
    iFact[FACT_SIZE] = Fact[FACT_SIZE].inv();
    for(int i = FACT_SIZE; i; --i) {
        iFact[i-1] = iFact[i] * i;
    }
    return false;
}();

mint comb(int n, int k) {
    if (k == 0) return mint::raw(1);
    assert(n >= 0 && k >= 0);
    if (k > n) return mint::raw(0);
    return Fact[n] * iFact[n - k] * iFact[k];
}

mint icomb(int n, int k) {
    return iFact[n] * Fact[n - k] * Fact[k];
}

mint fact(int n) {return Fact[n];}
mint perm(int n, int k) {
    assert(0 <= n);
    return Fact[n] * iFact[n - k];
}

mint solve(int n, ll b, ll c) {
  if (b < 0 || c < 0) return 0;
  const int z = internal::ceil_pow2((2 * n + 3) * 4), sz = 1 << z;
  vector<mint> f(sz), g(sz), h(sz);
  f[0] = 1;
  rep(i, n + 1) g[4 * i + i % 2] = comb(n, i);
  rrep(i, sz - 4) g[i+4] += g[i];
  rrep(i, sz - 1) g[i+1] += g[i];
  internal::butterfly(g);
  mint coeff = 1;
  while(b || c) {
    int p = b & 1, q = c & 1;
    b >>= 1, c >>= 1;
    internal::butterfly(f);
    rep(i, sz) h[i] = f[i] * g[i];
    internal::butterfly_inv(h);
    f.assign(sz, 0);
    int x = p << 2 | q;
    rep(i, sz) if ((i & 5) == x) f[(i & ~5) >> 1] = h[i];
    coeff *= mint::raw(sz);
  }
  return f[0] / coeff;
}

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  ll b, c;
  cin >> n >> b >> c;
  mint ans = solve(n, b, c) - solve(n, b - 1, c) - solve(n, b, c - 1) + solve(n, b - 1, c - 1);
  cout << ans.val() << '\n';
}
0