結果

問題 No.1689 Set Cards
ユーザー Hideaki Ito
提出日時 2021-09-24 22:21:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,793 bytes
コンパイル時間 2,303 ms
コンパイル使用メモリ 198,948 KB
最終ジャッジ日時 2025-01-24 17:26:48
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 1 MLE * 1
other AC * 2 WA * 6 TLE * 2 MLE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

#define mint modint<mod2>
template <std::uint_fast64_t Modulus> class modint {
  using u64 = std::uint_fast64_t;

public:
  u64 a;

  constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
  constexpr u64 &value() noexcept { return a; }
  constexpr const u64 &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    u64 exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
  friend ostream& operator<<(ostream& os, const modint& m) {
    return os << m.value();
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> pw3(13);
  pw3[0] = 1;
  rep(i, 13) if(i) pw3[i] = pw3[i-1]*3;
  vector<int> B(n);
  rep(i, n) {
    int k; cin >> k;
    rep(j, k) {
      int c; cin >> c;
      c--;
      B[i] += pw3[c];
    }
  }
  vector<vector<mint>> dp(n+1, vector<mint>(pw3[12]));
  dp[0][0] = 1;
  rep(i, n) {
    rep(j, pw3[12]) {
      dp[i+1][j] += dp[i][j];
      int nx = 0;
      rep(k, 12) {
        int b = min(2, (j/pw3[k]%3) + (B[i]/pw3[k]%3));
        nx += b * pw3[k];
      }
      dp[i+1][nx] += dp[i][j];
    }
  }
  mint ans = 0;
  rep(j, pw3[12]) {
    bool ok = true;
    rep(k, 12) if(j/pw3[k]%3 == 1) ok = false;
    if(ok) ans += dp[n][j];
  }
  cout << ans-1 << endk;
  return 0;
}
0