結果

問題 No.3285 Chorus with Friends
コンテスト
ユーザー 沙耶花
提出日時 2025-09-26 22:28:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,209 ms / 3,000 ms
コード長 1,480 bytes
コンパイル時間 4,099 ms
コンパイル使用メモリ 260,032 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-09-26 22:28:29
合計ジャッジ時間 16,663 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000005
#define Inf64 1000000000000000001LL
mint solve(vector<vector<int>> a){
	int n = a.size(),m = a[0].size();
	if(m<=16){
		vector<mint> cur(1<<m,0);
		cur[0] = 1;
		
		rep(i,n){
			vector<mint> nex(1<<m);
			rep(j,1<<m){
				int c = 0;
				for(int k=m-1;k>=0;k--){
					if((j>>k)&1){
						if(c && a[i][k+1] != a[i][0]){
							c = 2;
							break;
						}
						c = 1;
					}
				}
				if(c<=1)nex[j] = 1;
			}
			
			vector<mint> ndp(1<<m);
			rep(j,1<<m){
				for(int T = j;T >= 0;T = (T-1)&j){
					ndp[j] += cur[T]*nex[j^T];
					if(T==0)break;
				}
			}
			cur = ndp;
		}
		return cur[(1<<m)-1];
	}
	else{
		vector<mint> dp(1<<n);
		dp.back() = 1;
		rep(i,m){
			vector<mint> ndp(1<<n);
			rep(j,1<<n){
				rep(k,n){
					if((j>>k)&1){
						int nj = j;
						if(i!=m-1 && a[k][i+1] != a[k][0])nj ^= 1<<k;
						ndp[nj] += dp[j];
					}
				}
			}
			swap(dp,ndp);
		}
		mint res = 0;
		rep(i,1<<n)res += dp[i];
		return res;
	}
	return 0;
}
int main(){
	
	int n,m;
	cin>>n>>m;
	vector<vector<int>> a(n,vector<int>(m));
	rep(i,n){
		rep(j,m)cin>>a[i][j];
	}
	mint ans = 0;
	rep(i,301){
		vector<vector<int>> t;
		rep(j,n){
			if(a[j][0]!=i)continue;
			t.push_back(a[j]);
		}
		if(t.size()==0)continue;
		ans += solve(t);
	}
	cout<<ans.val()<<endl;
	return 0;
}
0