結果

問題 No.2990 Interval XOR
ユーザー Ryuhei MoriRyuhei Mori
提出日時 2024-12-15 01:56:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,343 bytes
コンパイル時間 1,553 ms
コンパイル使用メモリ 78,976 KB
実行使用メモリ 16,848 KB
最終ジャッジ日時 2024-12-15 01:57:39
合計ジャッジ時間 48,535 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,496 KB
testcase_01 AC 2 ms
9,040 KB
testcase_02 AC 2 ms
8,576 KB
testcase_03 AC 2 ms
8,448 KB
testcase_04 AC 2 ms
10,496 KB
testcase_05 AC 2 ms
8,576 KB
testcase_06 AC 2 ms
10,496 KB
testcase_07 AC 2 ms
10,700 KB
testcase_08 AC 2 ms
10,496 KB
testcase_09 AC 2 ms
8,912 KB
testcase_10 AC 2 ms
10,496 KB
testcase_11 AC 2 ms
10,572 KB
testcase_12 AC 2 ms
10,496 KB
testcase_13 AC 7 ms
10,436 KB
testcase_14 AC 3 ms
10,496 KB
testcase_15 AC 14 ms
16,588 KB
testcase_16 AC 2 ms
16,716 KB
testcase_17 AC 7 ms
10,496 KB
testcase_18 AC 23 ms
10,496 KB
testcase_19 AC 4 ms
16,840 KB
testcase_20 AC 16 ms
10,496 KB
testcase_21 AC 3 ms
16,720 KB
testcase_22 AC 12 ms
10,496 KB
testcase_23 AC 3 ms
10,624 KB
testcase_24 AC 15 ms
10,496 KB
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
権限があれば一括ダウンロードができます

ソースコード

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