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>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll MOD = 998244353;
struct gc{
ll mask, id, sign;
};
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> adj(n);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--, b--;
adj[a]+=1<<b;
}
vector<ll> incomp(1<<n);
for(int i = 0; i < (1<<n); i++){
int ok = 0;
for(int j = 0; j < n; j++){
if((1<<j)&i){
ok|=adj[j];
}
}
incomp[i] = !bool(ok&i);
// cerr << bitset<4>(ok) << ' ' << bitset<4>(i) << "->" << incomp[i] << '\n';
}
vector<ll> sum(1<<n), dp(1<<n);
dp[0] = 1;
array<ll,2> parity = {MOD-1,1};
matrix<gc> gray(n);
gray[0] = {{0,0,0},{1,0,1}};
for(int i = 1; i < n; i++){
gray[i] = gray[i-1];
gray[i].push_back({gray[i].back().mask|(1<<i),i,1});
for(int j = gray[i-1].size()-1; j > 0; j--){
gc cur = gray[i-1][j];
cur.sign*=-1;
cur.mask=gray[i].back().mask+(1<<cur.id)*cur.sign;
gray[i].push_back(cur);
}
}
// for(auto i : gray.back())
// cout << bitset<4>(i.mask) << ' ' << i.id << ' ' << i.sign << '\n';
for(auto & i : gray){
i.erase(i.begin());
}
for(int mask = 1; mask < (1<<n); mask++){
vector<int> cur;
for(int j = 0 ; j < n; j++){
if(mask&(1<<j))
cur.push_back(j);
}
int p = 0, cursum = 0, sub = 0;
for(gc i : gray[__builtin_popcount(mask)-1]){
const int id = cur[i.id];
sub+=(1<<id)*i.sign;
cursum+=__builtin_popcount(adj[id]&mask)*i.sign;
p^=1;
// cerr << bitset<4>(mask) << "->" << bitset<4>(sub) << '\n';
const int comp = mask^sub;
dp[mask]+=parity[p]*dp[comp]*incomp[sub];
sum[mask]+=parity[p]*(cursum*dp[comp]%MOD+sum[comp])*incomp[sub];
dp[mask]%=MOD;
sum[mask]%=MOD;
}
}
cout << sum[(1<<n)-1] << '\n';
}
# | 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... |