ABC281G 题解

首先，我们会注意到显然如果存在长度为 ll 的路径，就一定会有一条长度为 l−1l-1 的路径，因为每一条边的长度都是 11。

因此我们考虑在图上按照最短路径分层分层（其实就是按照 BFS 序分层）。会发现分层以后正好满足动态规划的性质。设 fi,jf_{i,j} 表示在 ii 个节点中，最后一层有 jj 个节点的方案数，则有如下的等式：

fi,j=∑k=1i−jfi−j,k×(2k−1)j×2j(j−1)2×Cn−i+j−1jf_{i,j}= \sum^{i-j}_{k=1}\color{red}f_{i-j,k} \color{black}\times\color{green}(2^k-1)^j \color{black}\times\color{blue}2^{\frac{j(j-1)}{2}} \color{black}\times\color{purple}C^j_{n-i+j-1}

下面我们来一点点拆分。

首先，kk 表示倒数第二层的节点数量。

红色部分表示前面一层有 kk 个节点的方案数量。

绿色部分是由二项式定理得到的。

我们对于当前层的每一个节点 jj，都需要与至少一个 kk 连接。也就是说，答案就是这样：

∑x=1kCkx\sum^{k}_{x=1}C^x_k

这个式子的意义就是从 kk 个节点中选择 xx 个节点的答案的和。

根据二项式定理，这个式子可以化成上面绿色式子的底数。注意！这里的 xx 是从 11 开始的，所以要减 11。

对于每一个当前层上面的节点 jj，我们都有上面的式子，因此答案就是所有的结果的乘积，也就是 jj 次方。

蓝色部分是表示在这些边之间也能连边。虽然我们是按照最短路分层，但是我们依然可以在同一层的边之间连接，这并不会影响这些点的最短路。这些边总共有 j(j−1)2\frac{j(j-1)}{2} 条，于是再像上面一样跑一遍二项式定理，即可得到蓝色部分。

紫色部分是指我们的 jj 个节点有多少种选择方式。我们要有 i−ji-j 个节点是原来不可改变的，剩下的点都可以自由选择……吗？

别忘了，最后一个节点的长度要大于前面的所有节点，他不能被选择！

于是我们就得到了上面的答案。

最后的答案就是 fn,1f_{n,1}。

不对。这个时候我们会发现一个严重的问题：为什么输出都是 00 啊？！

观察答案，我们可以发现紫色的部分有锅。

要不把 i=n,j=1i=n,j=1 代入这个式子看看？会发现 n−i+j−1=n−n+1−1=0n-i+j-1=n-n+1-1=0。

这个时候回到上面，就会发现这个式子的一个重要要求就是最后一个点不能选。但是我们的答案其实就是第 nn 个点，所以我们要特判。

最后就是排列数的快速计算方法：

Cji=Cj−1i+Cj−1i−1C^i_j=C_{j-1}^i+C_{j-1}^{i-1}

这样我们来考虑一下复杂度：预处理 O(N2)O(N^2)，DP的循环 O(N3)O(N^3)，但是我们的答案的绿色部分会有一点问题，我们可以预处理（用快速幂枚举所有的 jj 和 kk），也可以直接在循环的时候再算，所以答案的复杂度是 O(N3log⁡n)O(N^3\log n) 或者 O(N3)O(N^3)。反正时限大，都能过。

AC Code:

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
#include<iostream>
using namespace std;
const int N=600;
int MD;
typedef long long ll;
ll C[N][N],p2[N*N],f[N][N];
ll fast(ll n,ll p){ll s=n,ans=1;while(p){if(p&1)ans*=s;ans%=MD;s*=s;s%=MD;p>>=1;}return ans;}
void init(){
    C[1][0]=C[1][1]=C[0][1]=1;
    for(int i=2;i<N;i++){
        C[i][0]=C[0][i]=1;
        for(int j=1;j<=i;j++){
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MD;
        }
    }
    p2[0]=1;
    for(int i=1;i<N*N;i++){
        p2[i]=(p2[i-1]<<1)%MD;
    }
}

int main(){
    int n;
    cin>>n>>MD;
    init();
    f[1][1]=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<i;j++){
            for(int k=1;k<=i-j;k++){
                f[i][j]=f[i][j]+f[i-j][k]*fast(p2[k]-1,j)%MD*p2[j*(j-1)/2]%MD*C[n-i+j-1][j]%MD;
                f[i][j]%=MD;
              
            }
            // cout<<n-i+j-1<<" ";
            // cout<<i<<" "<<j<<" "<<f[i][j]<<endl;
        }
    }
    cout<<f[n][1]<<endl;
}