結果

問題 No.753 最強王者決定戦
コンテスト
ユーザー zengyongxu-jerry
提出日時 2026-06-24 23:13:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 67 ms / 1,000 ms
コード長 1,712 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,275 ms
コンパイル使用メモリ 331,500 KB
実行使用メモリ 11,388 KB
最終ジャッジ日時 2026-06-24 23:13:49
合計ジャッジ時間 3,661 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 16, M = 1 << 16;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;

int a[N][N];
ll f[N][M];

int ppc(int x){
	return __builtin_popcount(x);
}
bool check(int m){
	if (m == 0) return false;
	int k = ppc(m);
	return (k & (-k)) == k;
}

int get(int aa, int bb){
	if (aa < bb) return a[aa][bb];
	return -a[bb][aa];
}
//int get(int aa, int bb){
//	return a[min(aa, bb)][max(aa, bb)];
//}

void init(){
}
void solve(){
	for (int i = 0; i < 16; i ++ )
		for (int j = 0; j < 16; j ++ )
			cin >> a[i][j];
	for (int i = 0; i < 16; i ++ ) f[i][1 << i] = 1;
	for (int m = 0; m < (1 << 16); m ++ ){
		if (!check(m)) continue;
		for (int l = m; l; l = (l - 1) & m){
			if (ppc(l) != ppc(m) / 2) continue;
			int r = (m ^ l);
			if (l > r) continue;
			
			int qwq = l;
			while (qwq){
				int lw = __lg(qwq & (-qwq)), pwp = r;
				while (pwp){
					int rw = __lg(pwp & (-pwp));
					if (get(lw, rw) == 1) f[lw][m] += 2 * f[lw][l] * f[rw][r];
					else f[rw][m] += 2 * f[lw][l] * f[rw][r];
					pwp -= (1 << rw);
				}
				qwq -= (1 << lw);
			}
		}
	}
	for (int i = 0; i < 16; i ++ ) cout << f[i][(1 << 16) - 1] << "\n";
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while (T -- ) init(), solve();
}

/*

f[i][mask] 表示 i 在 mask 中胜出，其中 popcount(mask) = 2^k
样例咋不对啊。
哦我们 l vs r 和 r vs l 都会算 
哦不对这确实是两个 
卡卡常数，感觉跑的很慢啊。
首先我们 l vs r 和 r vs l 分开算，然后贡献 *2 
我去快很多啊 
拼一把 

*/
0