题目传送门

（题目非原创）

一. 思路

没有连通性限制的情况

fi,jf_{i, j}：ii 个点所有连边情况的简单无向图（无重边自环，不要求连通），每种情况边数 jj 次方的和。

考虑 ff 的递推式，因为没有连通性要求，边随便连，可以考虑每加入一个点，他和其他所有点的连边情况，显然，如果原来有 i−1i - 1 个点，加入一个点，新连边的所有情况 {C⁡i−10×新连0边C⁡i−11×新连1边⋯C⁡i−1i−1×新连i-1边\begin{cases}\operatorname{C}_{i-1}^{0}\times\text{新连0边}\\\operatorname{C}_{i-1}^{1}\times\text{新连1边}\\\cdots\\\operatorname{C}_{i-1}^{i-1}\times\text{新连i-1边}\\\end{cases}，设集合 Ti={C⁡i−10个0C⁡i−11个1⋯C⁡i−1i−1个i-1T_i=\begin{cases}\operatorname{C}_{i-1}^{0}\text{个0}\\\operatorname{C}_{i-1}^{1}\text{个1}\\\cdots\\\operatorname{C}_{i-1}^{i-1}\text{个i-1}\\\end{cases}，集合 FiF_i 表示 ii 个点所有连边情况的简单无向图的边数构成的集合。那么：

∵Fi={z∣z=x+y,x∈Fi−1,y∈Ti}&fi,j=∑z∈Fizj∴fi,j=∑x∈Fi−1∑y∈Ti(x+y)j\begin{gather} \because F_i=\left\{z\mid z=x+y,x\in F_{i-1},y\in T_i\right\}\\ \And f_{i,j}=\sum\limits_{z\in F_i}z^j\\ \therefore f_{i,j}=\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}(x+y)^j\\ \end{gather}

fi,jf_{i,j} 对于不同的 jj 继续拆解这个式子：

fi,0=∑x∈Fi−1∑y∈Ti(x+y)0=∑x∈Fi−1∑y∈Ti1=∣Fi−1∣∣Ti∣=fi−1,0×2i−1\begin{gather} f_{i,0}=\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}(x+y)^0\\ =\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}1\\ =\left|F_{i-1}\right|\left|T_{i}\right|\\ =f_{i-1,0}\times2^{i-1}\\ \end{gather}

fi,1=∑x∈Fi−1∑y∈Ti(x+y)1=∑y∈Ti∑x∈Fi−1x+∑x∈Fi−1∑y∈Tiy=∣Ti∣∑x∈Fi−1x+∣Fi−1∣∑y∈Tiy=2i−1×fi−1+fi−1,0×∑y∈Tiy\begin{gather} f_{i,1}=\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}(x+y)^1\\ =\sum\limits_{y\in T_{i}}\sum\limits_{x\in F_{i-1}}x+\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}y\\ =\left|T_{i}\right|\sum\limits_{x\in F_{i-1}}x+\left|F_{i-1}\right|\sum\limits_{y\in T_{i}}y\\ =2^{i-1}\times f_{i-1}+f_{i-1,0}\times\sum\limits_{y\in T_{i}}y\\ \end{gather}

fi,2=∑x∈Fi−1∑y∈Ti(x+y)2=∑x∈Fi−1∑y∈Ti(x2+y2+2xy)=∑y∈Ti∑x∈Fi−1x2+∑x∈Fi−1∑y∈Tiy2+2∑x∈Fi−1x∑y∈Tiy=2i−1×fi−1,2+fi−1,0×∑y∈Tiy2+2×fi−1,1×∑y∈Tiy\begin{gather} f_{i,2}=\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}(x+y)^2\\ =\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}(x^2+y^2+2xy)\\ =\sum\limits_{y\in T_{i}}\sum\limits_{x\in F_{i-1}}x^2+\sum\limits_{x\in F_{i-1}}\sum\limits_{y\in T_{i}}y^2+2\sum\limits_{x\in F_{i-1}}x\sum\limits_{y\in T_{i}}y\\ =2^{i-1}\times f_{i-1,2}+f_{i-1,0}\times \sum\limits_{y\in T_{i}}y^2+2\times f_{i-1,1}\times \sum\limits_{y\in T_{i}}y \end{gather}

可以预处理出 2i2^i、∑y∈Tiy\sum\limits_{y\in T_{i}}y 和 ∑y∈Tiy2\sum\limits_{y\in T_{i}}y^2。

有连通性限制的情况

di,jd_{i, j}：ii 个点所有保证连通的连边情况的简单无向图，每种情况边数 jj 次方的和。

DiD_i：ii 个点所有保证连通的连边情况的简单无向图的边数构成的集合。

正难则反，不方便直接推出符合条件的情况，可以用总的情况减去不符合的情况。随意选一个点作为基准，枚举这个点所在连通块的大小，显然这个点所在连通块一定连通~~（废话）~~，剩余点连通性随意，如果节点总数 ii 基准节点所在连通块大小为 kk，除去那个基准节点一定被选，剩余点中要选 k−1k-1 个作为连通块中的其他节点，方案数 C⁡i−1k−1\operatorname{C}_{i-1}^{k-1}。

di,j=fi,j−∑k=1k<i(C⁡i−1k−1×∑z∈{z∣z=x+y,x∈Dk,y∈Fi−k}zj)=fi,j−∑k=1k<i(C⁡i−1k−1×∑x∈Dk∑y∈Fi−k(x+y)j)\begin{gather} d_{i,j}=f_{i,j}-\sum\limits_{k=1}^{k<i}\left(\operatorname{C}_{i-1}^{k-1}\times\sum_{z\in\left\{z\mid z=x+y,x\in D_k,y\in F_{i-k}\right\}}z^j\right)\\ =f_{i,j}-\sum\limits_{k=1}^{k<i}\left(\operatorname{C}_{i-1}^{k-1}\times\sum\limits_{x\in D_k}\sum\limits_{y\in F_{i-k}}(x+y)^j\right) \end{gather}

道理和无连通性限制的情况是相同的。

这里为了偷懒节约篇幅 di,jd_{i,j} 对于不同的 jj 的具体过程就不写了，只写最终式，如果读者真正明白了 fi,jf_{i,j} 的推导是可以自己推出 di,jd_{i,j} 的。

di,0=fi,0−∑k=1k<i(C⁡i−1k−1×dj,0×fi−j,0)d_{i,0}=f_{i,0}-\sum\limits_{k=1}^{k<i}\left(\operatorname{C}_{i-1}^{k-1}\times d_{j,0}\times f_{i-j,0}\right)

di,1=fi,1−∑k=1k<i(C⁡i−1k−1×(fi−j,0×dj,1+dj,0×fi−j,1))d_{i,1}=f_{i,1}-\sum\limits_{k=1}^{k<i}\left(\operatorname{C}_{i-1}^{k-1}\times(f_{i-j,0}\times d_{j,1}+d_{j,0}\times f_{i-j,1})\right)

di,2=fi,2−∑k=1k<i(C⁡i−1k−1×(fi−j,0×dj,2+dj,0×fi−j,2+2×dj,1×fi−j,1))d_{i,2}=f_{i,2}-\sum\limits_{k=1}^{k<i}\left(\operatorname{C}_{i-1}^{k-1}\times(f_{i-j,0}\times d_{j,2}+d_{j,0}\times f_{i-j,2}+2\times d_{j,1}\times f_{i-j,1})\right)

二.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 2e3;

int mod, C[MAXn + 10][MAXn + 10], row1[MAXn + 10], row2[MAXn + 10], sum[MAXn + 10], sumpower[MAXn + 10], power2[MAXn + 10];
void Init(int top) {
    for (int i = 0; i <= top; ++i) {
        C[i][0] = C[i][i] = 1;
        row1[i] = i; row2[i] = (i * i) % mod;
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
            row1[i] = (row1[i] + C[i][j] * j) % mod;
            row2[i] = (row2[i] + C[i][j] * (j * j) % mod) % mod;
        }
    }
    power2[0] = 1;
    for (int i = 1; i <= top; ++i) {
        sum[i] = (sum[i - 1] + i) % mod;
        sumpower[i] = (sumpower[i - 1] + i * i) % mod;
        power2[i] = (power2[i - 1] * 2) % mod;
    }
}


int n, d[MAXn + 10][3], f[MAXn + 10][3];
signed main() {
    cin >> n >> mod;
    Init(n);
    f[1][0] = d[1][0] = 1;
    f[1][1] = f[1][2] = d[1][1] = d[1][2] = 0;
    for (int i = 2; i <= n; ++i) {
        f[i][0] = (f[i - 1][0] * power2[i - 1]) % mod;
        f[i][1] = ((f[i - 1][1] * power2[i - 1]) % mod + (f[i - 1][0] * row1[i - 1]) % mod) % mod;
        f[i][2] = ((f[i - 1][2] * power2[i - 1]) % mod + (f[i - 1][0] * row2[i - 1]) % mod + (2 * f[i - 1][1]) % mod * row1[i - 1] % mod) % mod;
        d[i][0] = f[i][0];
        d[i][1] = f[i][1];
        d[i][2] = f[i][2];
        for (int j = 1; j < i; ++j) {
            d[i][0] = (d[i][0] - (C[i - 1][j - 1] * (d[j][0] * f[i - j][0] % mod) % mod)) % mod;
            d[i][1] = (d[i][1] - (C[i - 1][j - 1] * ((f[i - j][0] * d[j][1] % mod) + (d[j][0] * f[i - j][1] % mod)) % mod)) % mod;
            d[i][2] = (d[i][2] - (C[i - 1][j - 1] * ((f[i - j][0] * d[j][2] % mod) + (d[j][0] * f[i - j][2] % mod) + (2 * d[j][1] * f[i - j][1] % mod)) % mod)) % mod;
        }
    }
    cout << (d[n][2] % mod + mod) % mod << '\n';
}