题目概述
给定 \(n\)，连边方式 \(i\) 连向 \(j\) 满足 \(1\leq i<j\leq n\)。
求对于 \(k\in[0,n]\)，恰好有 \(k\) 个点 \(x\) 满足 \(1\rightarrow x\rightarrow n\)。
数据范围：\(1\leq n\leq 2000\)，模数 \(P\) 任意。
分析
考虑 \(k=0\) 的情况，我们只需要用所有情况 \(2^{\binom{n}{2}}\) 减去 \(k=1,2,\dots,n\) 的答案即可。
考虑 \(k=1\) 的情况，因为 \(n\geq 2\)，所以如果有点满足条件，那么一定有 \(1,n\)，故满足点的数量不小于 \(2\)，此答案为 \(0\)。
现在考虑 \(k\geq 1\) 的情况，即至少有 \(1\) 个满足条件的点。
我们将这些点依据我们的条件分成几个类型：
- 满足条件的点，即能从 \(1\) 到且能到 \(n\)。
- 能从 \(1\) 到但是不能达到 \(n\)。
- 不能从 \(1\) 到达。
考虑第一个类型，发现这样的点满足入度和出度都不为 \(0\)，考虑用容斥计算这一部分的贡献（方案）。
设 \(f_{i,j}\) 表示现在有 \(i\) 个点，钦定了 \(j\) 个点的出度为 \(0\)，那么有：\(f_{1,0}=1,f_{i,j}=(f_{i-1,j-1}+f_{i-1,j})\times(2^{i-j-1}-1)\)。这是因为前面任意一个点都可以向当前点 \(i\) 连边，当然不能不连（入度不为 \(0\)）。
考虑类型二，发现与类型一有共性，故放在一起考虑，并设 \(g_{i,j}\) 表示有 \(i\) 个全都是类型一、二的点中有 \(j\) 个类型一的点的方案，则：\(g_{1,1}=1,g_{i,j}=g_{i-1,j-1}+g_{i-1,j}\times(2^{i-1}-1)\)。这是因为先撇开类型一（因为已经计算过了），当我这个点是类型二时，那么我可以让前面任意一个点与其连边。
这里的定义应当使最后一个点钦定为类型一的，故这个转移过后的 \(g_{i,j}\) 是定义的 \(g_{i,j}\)。我们令转移过后的为 \(g_2\)
考虑类型三，直接设 \(h_{i,j}\) 表示有 \(i\) 个点 \(j\) 个类型三的点的方案，那么：\(h_{1,0}=1,h_{i,j}=h_{i-1,j}+h_{i-1,j-1}\times(2^{n-i}-1)\)。这个可以向后面任意连边。
由于 \(n\) 一定不是类型三的点，故只需要枚举到 \(n-1\) 即可。
最后枚举类型一、类型三的点的个数就行了，即：
代码
时间复杂度 \(\mathcal{O}(n^2)\)。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 2005
using namespace std;
int n,mod,Pow2[N] = {1},f[N][N],g[N][N],h[N][N],F[N],ans[N];
signed main(){cin >> n >> mod;for (int i = 1;i <= n;i ++) Pow2[i] = Pow2[i - 1] << 1,Pow2[i] %= mod;f[1][0] = 1;for (int i = 2;i <= n;i ++) {f[i][0] = f[i - 1][0] * (Pow2[i - 1] - 1 + mod) % mod;for (int j = 1;j <= i;j ++) f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) * (Pow2[i - j - 1] - 1 + mod) % mod;}for (int i = 2;i <= n;i ++) for (int j = 0,t = 1;j <= i;j ++,t = -t) F[i] = (F[i] + (t * f[i][j] % mod + mod) % mod) % mod;h[1][0] = 1;for (int i = 2;i < n;i ++) {h[i][0] = 1;for (int j = 1;j <= i;j ++) h[i][j] = (h[i - 1][j] + h[i - 1][j - 1] * Pow2[n - i] % mod) % mod;}g[1][1] = 1;for (int i = 2;i < n;i ++)for (int j = 1;j <= i;j ++) g[i][j] = (g[i - 1][j - 1] + g[i - 1][j] * (Pow2[i - 1] - 1 + mod) % mod) % mod;for (int i = 2;i <= n;i ++)for (int j = 0;j <= n - i;j ++) ans[i] = (ans[i] + g[n - j - 1][i - 1] * h[n - 1][j] % mod) % mod;int s = 1;for (int i = 1;i <= n * (n - 1) / 2;i ++) s <<= 1,s %= mod;for (int i = 2;i <= n;i ++) ans[i] = ans[i] * F[i] % mod,s = (s + mod - ans[i]) % mod;cout << s;for (int i = 1;i <= n;i ++) printf(" %lld",ans[i]);return 0;
}