# CEOI2019 Day2 T1 CF1193A Amusement Park

@zryabc  July 29, 2019

#### 题目

You have been hired to supervise the project of a new amusement park. The park will have a special gimmick: directed slides that can get customers from one attraction to another quickly and in an entertaining way.

The park owner has given you the current project: a list of planned attractions and a list of slides that should be built between them. However, him being a businessman, he casually envisioned the impossible: among other things, he projected a slide coming from the Haunted Castle to the Roller Coaster, another from the Roller Coaster to the Drop Tower, and a third from the Drop Tower to the Haunted Castle. As the slides can only go downhill, it is evident why this is a problem. You don't have the luxury of ignoring the laws of physics when building the park, so you have to request changes in the project. Maybe he would accept reversing the slide between the Drop Tower and the Haunted Castle?

Formally:

• The project is a list of attractions and a list of directed slides. Each slide starts at one attraction and ends at another attraction.
• A proposal is obtained from the project by reversing the directions of some slides (possibly none or all of them).
• A proposal is legal if there is a way to assign an elevation to each attraction in such a way that every slide goes downhill.
• The cost of a proposal is the number of slides whose directions were reversed.

For a given project, find and report the sum of costs all legal proposals. Since this number may be large, output it modulo $998244353​$

n个点，m条边的有向图，边方向由你决定。问有使图无环的方案的贡献之和。

#### 思路

##### 正解

Paulliant考场打出了正解，先%一下。

#### 代码

#include<bits/stdc++.h>
#define LL long long
#define have(x,y) (((x)>>((y)-1))&1)
using namespace std;
const int P=998244353;
int n,m;
int U[405],V[405];
LL dp[1<<18|5];int cnt[1<<18|5];
bool mark[1<<18|5];
x+=y;
if(x>=P)x-=P;
if(x<0)x+=P;
}
void Solve(){
cnt[0]=-1;for(int i=1;i<1<<n;i++)cnt[i]=-cnt[i&(i-1)];
dp[0]=1;
for(int i=1;i<1<<n;i++)
for(int j=1;j<=m;j++)
if(have(i,U[j]) and have(i,V[j])){
mark[i]=true;break;
}
for(int i=1;i<1<<n;i++)
for(int j=i;j>=1;j=(j-1)&i)
printf("%lld\n",dp[(1<<n)-1]*m%P*499122177%P);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d",&U[i],&V[i]);
Solve();
return 0;
}