很 educational 的题。
题意:给出一个数 \(n\) 和模数,问有多少个 \(n\) 个点的有向图,满足图中无环,且不存在 \(a,b,c\) 满足 \(a\) 不可以到 \(b\),\(b\) 不可以到 \(c\),\(c\) 不可以到 \(a\)。
做法:
正着可能可以对这样的图进行描述,但是相当麻烦,我们考虑对不可达关系进行建边,发现这样得到的图比竞赛图还要强,并且和原图是一一对应的,竞赛图的一些性质还在这个图上符合:
-
缩点之后是条链。
-
点数 \(> 2\) 的强连通分量一定有三元环。
而这个图上的三元环就是原题中的需要满足不存在的条件,所以就要求这个新图缩点后的每个 scc 大小都要 \(\le 2\)。
那么考虑 dp,\(dp_{i,j}\) 代表用了 \(i\) 个点,上一个 scc 的大小为为 \(j\) 的,我们这里为了方便,同时除掉了 \(n!\) 和 \(2^{\frac{n(n-1)}2}\),直接转移即可,记得两点之间必有连边,所以有些系数是这样的,如下:
\[dp_{i+1,1} = dp_{i, 1}\frac 1 {2^{i-1}}+dp_{i,2}\frac 1{2^{i-2}}
\]
\[dp_{i+2,2} = dp_{i, 1}\frac 1 {2^{2(i-1)}}+dp_{i,2}\frac 1{2^{2(i-2)}}
\]
给出代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e6 + 5;
int dp[maxn][3], n, mod;
int inv[maxn], revjc[maxn];
int cal(int x, int y) {return revjc[y] * inv[y * (y - 1) / 2 + x * y] % mod;
}
int qpow(int x, int k, int p) {int res = 1;while(k) {if(k & 1)res = res * x % p;x = x * x % p, k >>= 1;}return res;
}
signed main() {cin >> n >> mod;inv[0] = 1; revjc[0] = revjc[1] = 1;for (int i = 1; i <= 2 * n; i++)inv[i] = inv[i - 1] * (mod + 1) / 2 % mod;for (int i = 2; i <= 2 * n; i++)revjc[i] = (mod - mod / i) * revjc[mod % i] % mod;for (int i = 2; i <= n; i++)revjc[i] = revjc[i - 1] * revjc[i] % mod;dp[1][1] = cal(0, 1), dp[2][2] = cal(0, 2);for (int i = 1; i <= n; i++) {for (int x = 1; x <= 2; x++)for (int y = 1; y <= 2; y++)dp[i + y][y] = (dp[i + y][y] + dp[i][x] * cal(x, y)) % mod;}int res = (dp[n][1] + dp[n][2]) % mod;for (int i = 1; i <= n; i++)res = res * i % mod;cout << res * qpow(2, n * (n - 1) / 2, mod) % mod << endl;return 0;
}