题解：AT_abc389_g [ABC389G] Odd Even Graph
Mr_Terminator
·
·
题解
如果你想保证今后你能够见了计数有可能切，耐心读完，不要只看转移公式。
我有一个 O(n^7) 的做法（与其他做法一样常数极小），这里来介绍一下。
首先我们可以想到一个非常明显的方法：一层一层 dp。我们可以观察到每一层的点离 1 号点的距离相同，它们之间随便连边，而下一层每个点都能通过上一层连边过来。距离差 \ge 2 的层之间没有连边。
然后我们发现**同一层之间随便连边**的方案数已经够不好处理了，相邻两层连边还要考虑**后面的一层每个点**是不是**都被前面一层的点连了**，非常难缠。
于是我们微调一下 $dp$ 状态：$dp_{i,j,k,l,T}$ 表示使用 $n$ 以内的 $i$ 个结点构成，最后一层有 $j$ 个点，离 $1$ 号点距离为偶数（即在偶数层）的结点数量为 $k$，**指定了 $l$ 条边可以随便选择连接或不连接**，最后一层离 $1$ 号点距离与 $T$ 模 $2$ 同余的方案数。
我们假设上一层有 $j$ 个点，除去这一层总共已选 $i$ 个点和 $l$ 条**自由边**，这一层有 $j_1$ 个点，那么选择这 $j_1$ 个点有 $C_{n-i}^{j_1}$ 种方法。
接着我们可以看出，这个 $dp$ 状态，非常容易讨论**同一层之间随便连边**的情况。这部分由上一层转移到这一层只用丢进去 $\frac{1}{2}j_1(j_1-1)$ 条自由边即可。
但是，**后面的一层每个点都被前面一层的点连了**这个不好处理。知道一点容斥的人可以立即看出，我们钦定这 $j_1$ 个点里面有 $j_2$ 个与上一层连通性不限制，$j_1-j_2$ 个**不连通**，那么这 $j_1-j_2$ 个点与上一层之间必然没有连边，而剩下 $j_2$ 个点与上一层的 $j$ 个点随意连边，贡献 $j_2j$ 条自由边。最后乘上容斥系数 $(-1)^{j_1-j_2}C_{j_1}^{j_2}$，这样就好转移了。
总体来说，转移方程如下：
$$\forall i,j,k,l,T,j_1\ge 1,0\le j_2\le j_1,(-1)^{j_1-j_2}C_{j_1}^{j_2}C_{n-i}^{j_1}dp_{i,j,k,l,T}\rightarrow dp_{i+j_1,j_1,k+Tj_1,l+\frac{1}{2}j_1(j_1-1)+j_2j,1-T}$$
边界条件即为 $dp_{1,1,1,0,0}=1$。
转移完毕后，我们设 $f_i=\sum\limits_{j,T}dp_{n,j,\frac{n}{2},i,T}$，也就是满足题目的条件情况下有 $i$ 条**自由边**的方案数。最后，有切切实实的 $i$ 条边方案数就是：
$$\sum\limits_{j\ge i}C_j^i f_j$$
完结撒花。
我们分析一下时间复杂度：枚举出 $i,j,k,l$ 总共有 $O(n^5)$ 种情况，然后枚举 $j_1,j_2$ 只有 $O(n^2)$ 种情况，转移时间复杂度就是 $O(n^7)$。统计的话时间复杂度为 $O(n^4)$，不是瓶颈。
最终时间复杂度就是 $O(n^7)$，暴打一切 $O(n^8)$。
代码如下：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,modp,C[455][455],dp[35][35][35][905][2],fuck[905];
signed main(){
cin>>n>>modp;dp[1][1][1][0][0]=1;
for(int i=0;i<=450;i++){
C[i][0]=1;for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%modp;
}
for(int i=1;i<n;i++){
for(int j=1;j<=i;j++){
for(int k=1;k<=i;k++){
for(int L=0;L<=i*(i-1)/2;L++){
for(int jj=1;jj<=n-i;jj++){
for(int kk=0;kk<=jj;kk++)for(int o=0;o<2;o++)(dp[i+jj][jj][k+o*jj][L+kk*j+jj*(jj-1)/2][o^1]+=dp[i][j][k][L][o]*((jj-kk)%2==1?modp-C[jj][kk]:C[jj][kk])%modp*C[n-i][jj])%=modp;
}
}
}
}
}
for(int i=0;i<=n*(n-1)/2;i++)for(int j=1;j<=n;j++)(fuck[i]+=dp[n][j][n/2][i][0]+dp[n][j][n/2][i][1])%=modp;
for(int i=n-1;i<=n*(n-1)/2;i++){
int ans=0;
for(int j=i;j<=n*(n-1)/2;j++)ans=(ans+fuck[j]*C[j][i])%modp;
cout<<ans<<' ';
}
return 0;
}
```