和 CF1657E 的做法十分相似

題目鏈接：G - Farthest City

題目大意：問有多少個 \(n(3\le n\le 500)\) 個點的無向連通圖滿足，若設 \(1\) 到 \(i\) 的最短路距離為 \(dis_i\)，則 \(dis_n\) 嚴格大于其它所有的 \(dis_i\)。輸出方案數對 \(M(10^8\le M \le 10^9)\) 取模。

考慮最短路的值一定是連續的，那么若最短路為 \(i\) 的點數有 \(c_i\) 個，且 \(dis_n=k\)，則方案數可以計算

其中，\(\sum_{i=0}^{k}c_i=n,c_0=c_k=1\)。\((2^{c_{i-1}}-1)^{c_i}\) 的含義為最短路為 \(i\) 的點是從最短路為 \(i-1\) 的點連接過來的，那么對于每個這樣的點，他可以選擇上一層的任意一個非空子集進行連接。\(2^{\binom{c_i}{2}}\) 的含義則是，對當前層的所有點，兩兩之間可以任意連接，對應可連接的邊數為 \(\binom{c_i}{2}\)，于是會有 \(2^{\binom{c_i}{2}}\) 的系數。

考慮背包，按最短路的值從小到大一批批安排當前點，那么有一個初始的 DP 想法，就是令 \(f_{i,j,k}\) 表示當前已經安排了 \(i\) 個點，目前最短路的最大值為 \(j\)，對應點的個數為 \(k\) 的方案數，那么枚舉最短路值為 \(j+1\) 的點的數量 \(cnt\)，可以轉移到 \(f_{i+cnt,j+1,cnt}\)，轉移系數為 \(\binom{n-1-i}{cnt}\times (2^{j}-1)^{cnt}\times 2^{\binom{cnt}{2}}\)。但是直接這樣做是 \(O(n^4)\) 的。

發現轉移系數與 \(j\) 無關，所以這一維可以直接省去，于是 DP 方式就變成，設 \(f_{i,j}\) 表示當前已經安排了 \(i\) 個點，且目前最短路最大的點數為 \(j\) 的方案數，那么同樣枚舉下一層的點數 \(k\)，就能轉移到 \(f_{i+k,k}\)，轉移系數為 \(\binom{n-1-i}{k}\times (2^{j}-1)^{k}\times 2^{\binom{k}{2}}\)。初始值設 \(f_{1,1}=1\)，最后答案即為 \(\sum_{j=1}^{n-1} f_{n-1,j}\times (2^j-1)\)。

#include<bits/stdc++.h>
using namespace std;
#define N 510
#define LL long long
int n,MOD,f[N][N],c[N][N],p[N*N],ans;
LL qow(LL x,LL y){return y?(y&1?x*qow(x,y-1)%MOD:qow(x*x%MOD,y/2)):1;}
int main()
{
	scanf("%d%d",&n,&MOD);
	p[0]=c[0][0]=1;
	for(int i=1;i<=n;i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++)
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
	}
	for(int i=1;i<=n*n;i++)p[i]=2ll*p[i-1]%MOD;
	f[1][1]=1;
	for(int i=1;i<n;i++)
	for(int j=1;j<=i;j++)if(f[i][j])
		for(int k=1;i+k<n;k++)
			f[i+k][k]=(f[i+k][k]+1ll*f[i][j]*c[n-i-1][k]%MOD*qow(p[j]+MOD-1,k)%MOD*p[k*(k-1)/2]%MOD)%MOD;
	for(int j=1;j<=n-1;j++)
		ans=(ans+1ll*f[n-1][j]*(p[j]+MOD-1)%MOD)%MOD;
	printf("%d\n",ans);
}

時間復雜度為 \(O(n^3 \log n)\)，預處理了 \(2^i\) 的值稍微進行了點常數優化。實際上是可以通過 \(O(n^2)\) 預處理每個 \((2^j-1)^k\) 的值把復雜度降到 \(O(n^3)\) 的，但是既然能過就不優化了。╮(╯▽╰)╭