結果

問題 No.2990 Interval XOR
ユーザー Ryuhei Mori
提出日時 2024-12-15 01:56:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,343 bytes
コンパイル時間 772 ms
コンパイル使用メモリ 76,628 KB
最終ジャッジ日時 2025-02-26 14:36:53
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22 TLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>

using i32 = int;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;

template <i32 MOD>
struct Mint {
  i32 n;
  constexpr Mint(i32 n = 0): n(n) {}
  constexpr Mint operator-() const { return Mint(n ? MOD - n: 0); }
  constexpr Mint &operator+=(const Mint &rhs){ n += rhs.n; if(n >= MOD) n -= MOD; return *this; }
  constexpr Mint &operator-=(const Mint &rhs){ if(rhs.n > n) n += MOD; n -= rhs.n; return *this; }
  constexpr Mint &operator*=(const Mint &rhs){ n = (i64) n * rhs.n % MOD; return *this; }
  constexpr Mint inv() const {
    i32 x = MOD;
    i32 y = n;
    i32 b = 0, d = 1;
    while(y){
      i32 q = x / y;
      x = x % y;
      b -= q * d;
      std::swap(x, y);
      std::swap(b, d);
    }
    if(b < 0) b += MOD;
    return b;
  }
  constexpr Mint &operator/=(const Mint &rhs){ n = (i64) n * rhs.inv().n % MOD; return *this; }
  friend constexpr Mint operator+(const Mint &lhs, const Mint &rhs){ return Mint(lhs) += rhs; }
  friend constexpr Mint operator-(const Mint &lhs, const Mint &rhs){ return Mint(lhs) -= rhs; }
  friend constexpr Mint operator*(const Mint &lhs, const Mint &rhs){ return Mint(lhs) *= rhs; }
  friend constexpr Mint operator/(const Mint &lhs, const Mint &rhs){ return Mint(lhs) /= rhs; }
  friend constexpr bool operator==(const Mint &lhs, const Mint &rhs){ return lhs.n == rhs.n; }
  friend constexpr bool operator!=(const Mint &lhs, const Mint &rhs){ return lhs.n != rhs.n; }
  friend std::ostream &operator<<(std::ostream &os, const Mint &rhs){ return os << rhs.n; }
};

constexpr u32 mod = 998244353;
using mint = Mint<mod>;

void hadamard(std::vector<mint> &v){
  u32 m = v.size();
  assert((m & (m-1)) == 0);
  for(u32 i = 1; i < m; i <<= 1){
    for(u32 j = 0; j < m; j++){
      if((i & j) == 0) std::tie(v[j], v[j+i]) = std::tuple<mint, mint>(v[j] + v[j+i], v[j] - v[j+i]);
    }
  }
}

int main(){
  u32 n, m;
  std::cin >> n >> m;

  std::vector<mint> v(1<<n, -mint((mod-1)>>n));
  for(u32 i = 0; i < m; i++){
    u32 l, r;
    std::cin >> l >> r;
    std::vector<mint> w(1<<n);
    for(u32 i = l; i <= r; i++) w[i] = 1;
    hadamard(w);
    for(i32 i = 0; i < (1<<n); i++) v[i] *= w[i];
  }
  hadamard(v);

  for(i32 i = 0; i < (1<<n); i++)
    std::cout << v[i] << '\n';

  return 0;
}
0