This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("popcnt")
#pragma GCC optimize("Ofast")
#define int long long
#define pii pair<int, int>
const int mod = 998244353;
int32_t main()
{
int n, m;
cin >> n >> m;
vector<bitset<20>> graph(n, 0);
vector<bitset<20>> dgraph(n, 0);
for (int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
a--; b--;
graph[a][b] = 1;
dgraph[a][b] = 1;
dgraph[b][a] = 1;
}
int N = 1<<n;
vector<pii> dp(N, {0,0});
dp[0] = {1, 0};
for (int i = 0; i < N; i++)
{
for (int j = 0; j < n; j++)
{
if (i&(1<<j)) continue;
int d = (graph[j]&(bitset<20>(i))).count();
int dd = (dgraph[j]&(bitset<20>(i))).count();
int h = __builtin_popcount(i)-dd;
int k = dp[i].first/(1<<h);
dp[i+(1<<j)].first += k;
dp[i+(1<<j)].first%=mod;
dp[i+(1<<j)].second += dp[i].second+k*d;
dp[i+(1<<j)].second%=mod;
}
}
cout << dp[N-1].second;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |