#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("Ofast")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define dauzhan gay
#define popcount __builtin_popcount
#define int long long
const long double Eps = 1e-12;
const int max1 = 1e9*1.4;
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 2e5 + 100;
const int B = 2e5 + 100;
const ll INF = 3e18 + 100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
if(y == 0) return 1;
if(y == 1) return x;
if(y % 2 == 0) {
ll now = binpow(x,y/2,md);
return (1ll*now*now) % md;
}
else {
ll now = binpow(x,y/2,md);
return (1ll*((1ll*now*now) % md)*x) % md;
}
}
/*
for(int i = 1;i <= n;i++) sp[0][i] = a[i];
for(int i = 1;i <= log2(n);i++) {
for(int l = 1;l <= n;l++) {
int r = l + (1 << i) - 1;
if(r > n) break;
int middle = l + (1 << (i - 1));
sp[i][l] = max(sp[i - 1][l],sp[i - 1][middle]);
}
}
int get(int l,int r) {
int g = log2(r - l + 1);
return max(sp[g][l],sp[g][r - (1 << g) + 1]);
}
*/
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
int n,m;
cin >> n >> m;
vector <pair <int,int> > reb;
vector <int> r[n + 1];
for(int i = 1;i <= m;i++) {
int u,v;
cin >> u >> v;
r[v].pb(u);
}
vector <int> v[n + 1];
for(int i = 0;i < (1 << n);i++) {
v[popcount(i)].pb(i);
}
int ans[(1 << n)] = {};
for(int i = 0;i < n;i++) {
for(int j = 1;j <= n;j++) {
for(auto mask:v[i]) {
if(mask&(1 << (j - 1))) continue;
int cnt = 0;
for(auto x:r[j]) {
if(mask&(1 << (x - 1))) continue;
cnt++;
}
ans[mask | (1 << (j - 1))]+=(ans[mask] + cnt);
ans[mask | (1 << (j - 1))]%=mod;
}
}
}
cout << ans[(1 << n) - 1] << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
