相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf
解题报告
首先我们要熟悉竞赛图的两个结论:
- 任意一个竞赛图一定存在哈密尔顿路径
- 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通
现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和
设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$
于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 2009; int n, MOD, f[N], g[N], pw[N * N], C[N][N]; inline int read() { char c = getchar(); int ret = 0, f = 1; while (c < '0' || c > '9') { f = c == '-'? -1: 1; c = getchar(); } while ('0' <= c && c <= '9') { ret = ret * 10 + c - '0'; c = getchar(); } return ret * f; } int main() { freopen("path.in", "r", stdin); freopen("path.out", "w", stdout); n = read(); MOD = read(); pw[0] = 1; for (int i = 1; i < n * n; i++) { pw[i] = (pw[i - 1] << 1) % MOD; } C[0][0] = 1; for (int i = 1; i <= n; ++i) { C[i][0] = 1; for (int j = 1; j <= n; j++) { C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD; } } f[0] = g[0] = 1; for (int i = 1; i <= n; i++) { f[i] = g[i] = pw[i * (i - 1) >> 1]; for (int j = 1; j < i; j++) { g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD; } } for (int x = 1; x <= n; x++) { int ans = 0; for (int i = 1; i <= x; i++) { ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD; } printf("%d\n", ans > 0? ans: ans + MOD); } return 0; }