#1176063 (C++23) No.1689 Set Cards

• 問題: No.1689 Set Cards
• ユーザー: Hydrogen332
• 提出日時: 2026-08-10 20:47:16
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 3 ms / 2,000 ms
• コード長: 3,903 bytes
• コンパイル時間: 941 ms
• コンパイル使用メモリ: 163,636 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-10 20:47:19
• 合計ジャッジ時間: 3,035 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

#include <cassert>
#include <concepts>
#include <iostream>
#include <type_traits>
#include <utility>
#include <vector>

// ======================================================================
// BEGIN library/math/modint.hpp (147 lines)
// ======================================================================

template <unsigned int MOD>
struct modint {
private:
  unsigned int v_;

public:
  constexpr modint() : v_(0) {}

  template <std::integral T>
  constexpr modint(T v) {
    if constexpr (std::is_signed_v<T>) {
      long long x = static_cast<long long>(v) % MOD;
      if (x < 0) {
        x += MOD;
      }
      v_ = static_cast<unsigned int>(x);
    } else {
      unsigned long long x = static_cast<unsigned long long>(v);
      if (x >= MOD) {
        x %= MOD;
      }
      v_ = static_cast<unsigned int>(x);
    }
  }

  constexpr unsigned int val() const {
    return v_;
  }

  constexpr modint& operator++() {
    ++v_;
    if (v_ == MOD) {
      v_ = 0;
    }
    return *this;
  }

  constexpr modint& operator--() {
    if (v_ == 0) {
      v_ = MOD;
    }
    --v_;
    return *this;
  }

  constexpr modint operator++(int) {
    modint res = *this;
    ++(*this);
    return res;
  }

  constexpr modint operator--(int) {
    modint res = *this;
    --(*this);
    return res;
  }

  constexpr modint operator+() const {
    return *this;
  }

  constexpr modint operator-() const {
    return (v_ == 0 ? *this : raw(MOD - v_));
  }

  constexpr modint& operator+=(const modint& rhs) {
    v_ += rhs.v_;
    if (v_ >= MOD) {
      v_ -= MOD;
    }
    return *this;
  }

  constexpr modint& operator-=(const modint& rhs) {
    if (v_ < rhs.v_) {
      v_ += MOD;
    }
    v_ -= rhs.v_;
    return *this;
  }

  constexpr modint& operator*=(const modint& rhs) {
    v_ = static_cast<unsigned long long>(v_) * rhs.v_ % MOD;
    return *this;
  }

  constexpr modint& operator/=(const modint& rhs) {
    return *this *= rhs.inv();
  }

  friend constexpr modint operator+(modint lhs, const modint& rhs) {
    return lhs += rhs;
  }

  friend constexpr modint operator-(modint lhs, const modint& rhs) {
    return lhs -= rhs;
  }

  friend constexpr modint operator*(modint lhs, const modint& rhs) {
    return lhs *= rhs;
  }

  friend constexpr modint operator/(modint lhs, const modint& rhs) {
    return lhs /= rhs;
  }

  constexpr modint inv() const {
    long long a = static_cast<long long>(v_), b = MOD;
    long long x = 1, y = 0;

    while (b) {
      const long long t = a / b;
      a -= t * b;
      std::swap(a, b);
      x -= t * y;
      std::swap(x, y);
    }

    assert(a == 1);
    if (x < 0) x += MOD;
    return raw(static_cast<unsigned int>(x));
  }

  constexpr modint pow(long long n) const {
    assert(0 <= n);

    modint x = *this;
    modint res = 1;

    while (n) {
      if (n & 1) {
        res *= x;
      }
      x *= x;
      n >>= 1;
    }

    return res;
  }

private:
  static constexpr modint raw(unsigned int v) {
    modint res;
    res.v_ = v;
    return res;
  }
};

// ======================================================================
// END library/math/modint.hpp
// ======================================================================

using namespace std;
using ll = long long;

using mint = modint<998244353>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    int K;
    cin >> K;

    for (int j = 0; j < K; j++) {
      int C;
      cin >> C;
      A[i] |= 1 << (C - 1);
    }
  }

  mint ans = 0;
  for (int S = 0; S < (1 << 12); S++) {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
      if ((A[i] & S) == S) cnt++;
    }

    int pc = 0;
    for (int i = 0; i < 12; i++) if ((S >> i) & 1) pc++;

    if (pc % 2 == 0) ans += mint(2).pow(cnt);
    else ans -= mint(2).pow(cnt);
  }

  cout << ans.val() << '\n';
}