Submission #468312

#	Time	Username	Problem	Language	Result	Execution time	Memory
468312		warner1129	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	359 ms	39364 KiB

amusementpark

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

template <uint32_t mod> struct modint {
	uint32_t val;
public:
	static modint raw(int v) { modint x; x.val = v; return x; }
	modint() : val(0) {}
	template <class T>
	modint(T v) { int64_t x = (int64_t)(v%(int64_t)(mod)); if (x < 0) x += mod; val = (uint32_t)(x); }
	modint(bool v) { val = ((unsigned int)(v) % mod); }
	modint& operator++() { val++; if (val == mod) val = 0; return *this; }
	modint& operator--() { if (val == 0) val = mod; val--; return *this; }
	modint operator++(int) { modint result = *this; ++*this; return result; }
	modint operator--(int) { modint result = *this; --*this; return result; }
	modint& operator+=(const modint& rhs) { val += rhs.val; if (val >= mod) val -= mod; return *this; }
	modint& operator-=(const modint& rhs) { val -= rhs.val; if (val >= mod) val += mod; return *this; }
	modint& operator*=(const modint& rhs) { uint64_t z = val; z *= rhs.val; val = (uint32_t)(z % mod); return *this; }
	modint& operator/=(const modint& rhs) { return *this = *this * rhs.inv(); }
	modint operator+() const { return *this; }
	modint operator-() const { return modint() - *this; }
	modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
	modint inv() const { return pow(mod-2); }
	friend modint operator+(const modint& lhs, const modint& rhs) { return modint(lhs) += rhs; }
	friend modint operator-(const modint& lhs, const modint& rhs) { return modint(lhs) -= rhs; }
	friend modint operator*(const modint& lhs, const modint& rhs) { return modint(lhs) *= rhs; }
	friend modint operator/(const modint& lhs, const modint& rhs) { return modint(lhs) /= rhs; }
	friend bool operator==(const modint& lhs, const modint& rhs) { return lhs.val == rhs.val; }
	friend bool operator!=(const modint& lhs, const modint& rhs) { return lhs.val != rhs.val; }
};

using mint = modint<998244353>;

const int maxn = 18;

mint g[1<<maxn][maxn+1], ig[1<<maxn][maxn+1];
int edge[maxn * maxn];
int n, m, lim;

bool check(const int &s) {
	for (int i = 1; i <= m; i++)
		if ((s & edge[i]) == edge[i])
			return false;
	return true;
}

void FWT() {
	for (int i = 1; i < lim; i<<=1)
		for (int j = 0; j < lim; j += (i<<1))
			for (int k = 0; k < i; k++)
				for (int p = 0; p <= n; p++)
					g[i | j | k][p] += g[j | k][p];
}

void INV() {
	for (int s = 1; s < lim; s++) {
		mint inv = ig[s][0] = g[s][0].inv();
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < i; j++)
				ig[s][i] -= ig[s][j] * g[s][i-j];
			ig[s][i] *= inv;
		}
	}
}

void IFWT() {
	for (int i = 1; i < lim; i<<=1)
		for (int j = 0; j < lim; j += (i<<1))
			for (int k = 0; k < i; k++)
				for (int p = 0; p <= n; p++)
					ig[i | j | k][p] -= ig[j | k][p];
}

void solve() {
	cin >> n >> m;
	lim = (1<<n);
	for (int i = 1, x, y; i <= m; i++)
		cin >> x >> y, --x, --y, edge[i] = ((1<<x) | (1<<y));
	g[0][0] = 1;
	for (int s = 1, cnt; s < lim; s++)
		if (check(s)) g[s][cnt] = (((cnt = __builtin_popcount(s)) & 1) ? mint(-1) : mint(1));
	FWT();
	INV();
	IFWT();	
	cout << (ig[lim-1][n] * mint(m) * mint(499122177)).val << '\n';
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'void solve()':
amusementpark.cpp:85:36: warning: operation on 'cnt' may be undefined [-Wsequence-point]
   85 |   if (check(s)) g[s][cnt] = (((cnt = __builtin_popcount(s)) & 1) ? mint(-1) : mint(1));
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37