洛谷 CF1193A Amusement Park

题目翻译

有一个游乐场有一个好玩的项目：一些有向滑梯可以将游客从一个景点快速、刺激地传送到另一个景点。现在，你要帮游乐场老板来规划一个造滑梯的项目。

滑梯只能从海拔高的地方向海拔低的地方滑。老板原定的方案已经给出，你的工作是反转某些滑梯的方向（可以反转全部的或一个都不转），并为每个景点指定一个海拔高度，使得每一个滑梯都能下山，那么这个方案是合法的。其成本是要反转的滑梯的总数。对于老板给定的方案，你需要算出所有合法方案的成本总和。由于这个数可能很大，所以输出时需将其对\(998,244,353\)取模。

输入格式

第一行包括两个用空格隔开的整数\(n,m(1\le n\le 18,0\le m\le n(n-1)/2)\)表示景点和滑梯的数量。景点从\(1-n\)编号。

之后的\(m\)行，第\(i\)行包括两个整数\(a_i,b_i(1\le a_i,b_i\le n)\)，表示从\(a_i\)到\(b_i\)有一条滑梯。数据保证无自环，无重边，无双向边。

输出格式

输出一行，表示答案。

子任务：

子任务1：（7分）\(n\le 3\)。

子任务2：（12分）\(n\le 6\)。

子任务3：（23分）\(n\le 10\)。

子任务4：（21分）\(n\le 15\)。

子任务5：（37分）无附加条件。

样例说明

在第一个样例中，有两种方案：

不反转任何滑梯，花费为0.
反转滑梯，花费为1.

因为所有方案都是合法的，所以答案为1.在第二个样例中，有8种方案如下：（括号中为花费）

\(1\to 2,2\to 3,1\to 3(0)\)
\(1\to 2,2\to 3,3\to 1(1)\)
\(1\to 2,3\to 2,1\to 3(1)\)
\(1\to 2,3\to 2,3\to 1(2)\)
\(2\to 1,2\to 3,1\to 3(1)\)
\(2\to 1,2\to 3,3\to 1(2)\)
\(2\to 1,3\to 2,1\to 3 (2)\)
\(2\to 1,3\to 2,3\to 1(3)\)

第二种方案是不合法的，因为会出现了一个从1到1的回路，制造了1点必须比自己高的悖论。同样地，第七种方案也是不合法的，所以答案是\(0+1+2+1+2+3=9\)。

题解：

作为本题第一个提交翻译的人（也不知道现在过没过）和第二个AC的人，先抢着发一下第一篇题解。

乍一看题面（因为是我翻译的）感觉题目爆难（事实上的确挺难的）。但是实际上我们不需要确定这张图的海拔高度到底是多少。我们只需要保证这张图没有环即可（由样例说明可以得出，环是绝对不合法的）。同理，我们可以证明，只要这个图不包含环，那么这个图就绝对是合法的。

那么题意就变成了：一张有向图，随便改边的方向，最终的答案是使图无环的贡献之和。

但是蒟蒻太弱了，自己只YY到了上面的步骤...

我们可以这样去想，对于一张图，我们可以把它拆成若干个DAG（有向无环图），这些DAG以点集的形式出现。确定一个DAG为初始集合。那么我们可以这样考虑：我们把剩下的DAG点集分批次加入到这个初始集合中，但是，DAG+DAG不一定还是DAG，所以我们在加入的时候进行判断。显然，假如我们新加入的点的出度或入度全部为0，那么这个加入后的原始集合就会依然合法。

注意这个关系是或！为什么呢？以为我们只要保证这些点的出度或者入度都为0，我们就可以保证：我们在链接的时候只连它们中度为0的那些，而那些度不为0的就无论如何也不会和原图构成环。

所以我们考虑采用DP来解决方案数的问题：设DP[a]为集合a为DAG的方案总数。

但是我们会出现：一个合法的小集合，我们既可以把它分多次依次加入，也可以把它一次性加入。

所以我们还需要利用容斥原理。

思路及代码借鉴自@zryabc's blog。

#include<bits/stdc++.h>

#define ll long long

#define check(x,y) (((x)>>((y)-1))&1)

using namespace std;

const int mod=998244353;

const int maxn=1<<18|5;

int n,m;

int u[405],v[405];

ll dp[maxn];

int cnt[maxn];

bool mark[maxn];

void add(ll &x,ll y)

{

    x+=y;

    if(x>=mod)

        x-=mod;

    if(x<0)

        x+=mod;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++)

        scanf("%d%d",&u[i],&v[i]);

    cnt[0]=-1;dp[0]=1;

    for(int i=1;i<1<<n;i++)

        cnt[i]=-cnt[i&(i-1)];

    for(int i=1;i<1<<n;i++)

        for(int j=1;j<=m;j++)

            if(check(i,u[j]) && check(i,v[j]))

            {

                mark[i]=1;

                break;

            }

    for(int i=1;i<1<<n;i++)

        for(int j=i;j>=1;j=(j-1)&i)

            if(!mark[j])

                add(dp[i],dp[i^j]*cnt[j]);

    printf("%lld\n",dp[(1<<n)-1]*m%mod*499122177%mod);

    return 0;

}

巴特西

CF1193A Amusement Park