代码

// TO TEST A 10s PROGRAM

#include <bits/stdc++.h>

using namespace std;

const int INF = 998244353;
const int inv2 = (INF + 1) / 2;
const int maxn = 18;

const int TAB[maxn][maxn] = {

{0,551298046,164717599,572562609,925735031,0,640870735,348685526,143374786,229551084,0,96027962,0,1317803,929289559,926742530,744280972}, 
{551298046,0,950783823,710740376,593861775,0,183658937,0,174298032,556967595,105810733,0,357074392,0,0,262257146,832911805}, 
{164717599,950783823,0,561364131,0,223830865,268673618,655311828,859428941,150372174,808199159,4768168,127485444,92800712,858394578,0,259086739}, 
{572562609,710740376,561364131,0,223066849,0,0,191135429,786759811,937060568,0,165142598,503693569,475543023,51002413,221944983,0}, 
{925735031,593861775,0,223066849,0,0,454345665,691812556,520864878,608641287,57669496,427025373,535017767,100063819,632414143,0,216789841}, 
{0,0,223830865,0,0,0,0,0,0,787281728,215582134,780382512,0,0,0,155683948,353420135}, 
{640870735,183658937,268673618,0,454345665,0,0,328099750,971279901,997086524,0,150078421,0,223268507,0,1403405,0}, 
{348685526,0,655311828,191135429,691812556,0,328099750,0,0,994937307,192304407,210193460,625109058,442656354,664756605,726082165,0}, 
{143374786,174298032,859428941,786759811,520864878,0,971279901,0,0,0,586495927,110098594,608900662,294403686,710486892,837367306,0}, 
{229551084,556967595,150372174,937060568,608641287,787281728,997086524,994937307,0,0,0,21448177,781753730,239369038,58089442,725507243,183031488}, 
{0,105810733,808199159,0,57669496,215582134,0,192304407,586495927,0,0,859284482,29902325,942695669,917375453,535432834,604209464}, 
{96027962,0,4768168,165142598,427025373,780382512,150078421,210193460,110098594,21448177,859284482,0,901754081,740409314,246781492,0,28826630}, 
{0,357074392,127485444,503693569,535017767,0,0,625109058,608900662,781753730,29902325,901754081,0,14004848,0,632444435,302817365}, 
{1317803,0,92800712,475543023,100063819,0,223268507,442656354,294403686,239369038,942695669,740409314,14004848,0,234882376,0,402382633}, 
{929289559,0,858394578,51002413,632414143,0,0,664756605,710486892,58089442,917375453,246781492,0,234882376,0,0,0}, 
{926742530,262257146,0,221944983,0,155683948,1403405,726082165,837367306,725507243,535432834,0,632444435,0,0,0,169502495}, 
{744280972,832911805,259086739,0,216789841,353420135,0,0,0,183031488,604209464,28826630,302817365,402382633,0,169502495,0}
} ;
typedef unsigned long long u64;

inline int qpow(int x, int y){
	int ret = 1;
	for(; y; y >>= 1, x = 1ll * x * x % INF){
		if(y & 1) ret = 1ll * ret * x % INF;
	}
	return ret;
}

int n, m, ans;
int w[maxn][maxn], inv[maxn + 2];
int sume[1 << maxn], cnte[1 << maxn], G[maxn + 2][1 << maxn], pop[1 << maxn];
int A[maxn + 2][1 << maxn], B[maxn + 2][1 << maxn], C[maxn + 2][1 << maxn]; 

inline void FMT(int *vec){
	for(int step = 1; step < m; step <<= 1){
		for(int i = 0; i < m; i += step << 1){
			int *p1 = vec + i, *p2 = vec + i + step;
			for(int j = 0; j < step; ++j, ++p1, ++p2) (*p2 += *p1) -= (*p2 >= INF ? INF : 0);
		}
	}
}

inline void IFMT(int *vec){
	for(int step = 1; step < m; step <<= 1){
		for(int i = 0; i < m; i += step << 1){
			int *p1 = vec + i, *p2 = vec + i + step;
			for(int j = 0; j < step; ++j, ++p1, ++p2) (*p2 -= *p1) += (*p2 < 0 ? INF : 0);
		}
	}
}

inline void recalc(){
	memset(G, 0, sizeof(G));
	for(int S = 1; S < m; ++S) G[pop[S]][S] = cnte[S];
	for(int i = 0; i <= n; ++i) FMT(G[i]);
	static int tmp[maxn + 2], a[maxn + 2];
	for(int S = 1; S < m; ++S){
		for(int i = 0; i <= n; ++i) a[i] = G[i][S];
		for(int i = 0; i < n; ++i){
			int *p1 = tmp, *p2 = a + i;
			u64 res = 0;
			for(int j = 0; j < i; ++j, ++p1, --p2) res += 1ll * (*p1) * (*p2);
			tmp[i] = (1ll * a[i + 1] * (i + 1) + INF - res % INF) % INF;
		}
		for(int i = 1; i <= n; ++i) G[i][S] = 1ll * tmp[i - 1] * inv[i] % INF;
	}
	for(int i = 0; i <= n; ++i) IFMT(G[i]);
	return;
}

int main(){
	// freopen("mst.in", "r", stdin);
	// freopen("mst.out", "w", stdout);
	
	// scanf("%d", &n);
	n = 17, m = (1 << n);
	vector<pair<int, int> > vec;
	for(int i = 0; i <= n; ++i) inv[i] = qpow(i, INF - 2);
	for(int S = 0; S < m; ++S) cnte[S] = 1, pop[S] = __builtin_popcount(S);
	
	int cnte2 = 1;
	
	for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j){
		// scanf("%d", &w[i][j]);
		w[i][j] = TAB[i][j];
		if(i < j && w[i][j]){
			vec.push_back(make_pair(i, j));
			cnte2 = 2ll * cnte2 % INF;
		}
	}
	sort(vec.begin(), vec.end(), [&](const pair<int, int> &ths, const pair<int, int> &oth){ return make_pair(w[ths.first][ths.second], ths) < make_pair(w[oth.first][oth.second], oth); });
	
	for(int i = 0; i < vec.size(); ++i){
		int u = vec[i].first, v = vec[i].second;
		cnte2 = 1ll * cnte2 * inv2 % INF;
		recalc();
		int res = 0;
		for(int S = 0; S < m; ++S) if((S >> u & 1) && (S >> v & 1))
			res = (res + 1ll * G[pop[S]][S] * cnte[((1 << n) - 1) ^ S]) % INF;
		res = (cnte[(1 << n) - 1] + INF - res) % INF;
		ans = (ans + 1ll * res * cnte2 % INF * w[u][v]) % INF;
		for(int S = 0; S < m; ++S) if((S >> u & 1) && (S >> v & 1))
			cnte[S] = 2ll * cnte[S] % INF;
	}
	
	printf("%d\n", ans);
	return 0;
}

评测结果