#1148326 (C++17) No.3486 Draw a Rainbow

• 問題: No.3486 Draw a Rainbow
• ユーザー: 👑 binap
• 提出日時: 2026-02-16 07:56:52
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 465 ms / 4,000 ms
• コード長: 3,991 bytes
• コンパイル時間: 4,972 ms
• コンパイル使用メモリ: 277,016 KB
• 実行使用メモリ: 6,500 KB
• 最終ジャッジ日時: 2026-03-27 20:55:51
• 合計ジャッジ時間: 12,325 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

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

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;

template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}

template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}

// zeta & mobius transform
// https://nyaannyaan.github.io/library/set-function/zeta-mobius-transform.hpp
template <typename T>
void superset_zeta_transform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        f[j] += f[j | i];
      }
    }
  }
}

template <typename T>
void superset_mobius_transform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        f[j] -= f[j | i];
      }
    }
  }
}

template <typename T>
void subset_zeta_transform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        f[j | i] += f[j];
      }
    }
  }
}

template <typename T>
void subset_mobius_transform(vector<T>& f) {
  int n = f.size();
  assert((n & (n - 1)) == 0);
  for (int i = 1; i < n; i <<= 1) {
    for (int j = 0; j < n; j++) {
      if ((j & i) == 0) {
        f[j | i] -= f[j];
      }
    }
  }
}

using mint = modint998244353;
int main(){
	int n, m, l;
	cin >> n >> m >> l;
	vector<mint> f(1 << l);
	f[0] = 1;
	vector<vector<int>> cnt(m, vector<int>(l));
	rep(i, n){
		int a, b;
		cin >> a >> b;
		a--; b--;
		cnt[a][b - m]++;
	}
	rep(i, m){
		vector<mint> g(1 << l);
		g[0] = 1;
		
		
		rep(j, l){
			mint coeff = (mint(2).pow(cnt[i][j]) - 1);
			vector<mint> g_old(1 << l);
			swap(g, g_old);
			rep(x, (1 << l)){
				g[x] += g_old[x];
				g[x | (1 << j)] += g_old[x] * coeff;
			}
		}
		g[0] = 0;
		
		subset_zeta_transform(f);
		subset_zeta_transform(g);
		
		vector<mint> h(1 << l);
		rep(x, (1 << l)) h[x] += f[x] * g[x];
		subset_mobius_transform(h);
		
		swap(f, h);
		
	}
	cout << f[(1 << l) - 1];
	return 0;
}