Submission #691941

#	Time	Username	Problem	Language	Result	Execution time	Memory
691941		beaboss	Amusement Park (CEOI19_amusementpark)	C++14	0 / 100	1 ms	300 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;


int MOD = 998244353;

int main() {
	int n, m;
	cin >> n >> m;

	vector<vector<int> > adj(n);

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;b--;
		adj[a].push_back(b);
	}

	vector<pair<int, int> > dp(1<<n, {0, 0});
	dp[0]={1, 0};
	for (int i = 0; i < n; i++) dp[(1 << i)] = {1, 0};
	for (int i = 1; i < (1<<n); i++) {
		// cout << i << dp[i].first << dp[i].second << endl;
		for (int ne = 0; ne < n; ne++) {
			if ((1 << ne) & i) continue;
			int c = 0;
			for (auto val: adj[ne]) {
				if ((1 << val) & i) {
					c++;
				}
			}

			dp[i^(1 << ne)].second=((dp[i^(1 << ne)].second)%MOD+(dp[i].second+dp[i].first*c)%MOD)%MOD;
			dp[i^(1 << ne)].first=(dp[i^(1 << ne)].first+dp[i].first)%MOD;
			// cout << i<<(ne) << dp[i^(1 << ne)].second << endl;
		}
	}
	cout << dp[(1<<n)-1].second << endl;

}

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