題目大意
給出一個 n n n個點的圖，現允許任意兩點之間建立長度為1的無向邊（不允許重邊），問有多少種建圖方案滿足1到 n n n的最短路距離為 K K K。 n , K ≤ 100 n,K\le100 n,K≤100
解題分析
很妙的DP！可以考慮對這個圖進行分層，第 i i i層上所有點的最短路距離都為 i i i，那麼1在第0層， n n n就在第 K K K層，每一層都隻能與上一層或這一層中的節點相連。設 f [ i ] [ j ] [ k ] f[i][j][k] f[i][j][k]為前 i i i層一共使用 j j j個節點，其中第 i i i層有 k k k個節點的合法方案。枚舉前一層有 x x x個，那麼明顯轉移方程為
f [ i ] [ j ] [ k ] = ∑ f [ i − 1 ] [ j − k ] [ x ] ∗ C n − j + k + 1 k ∗ ( 2 x − 1 ) k ∗ 2 C k 2 f[i][j][k]=\sum f[i-1][j-k][x]*C_{n-j+k+1}^{k}*(2^x-1)^k*2^{C_k^2} f[i][j][k]=∑f[i−1][j−k][x]∗Cn−j+k+1k∗(2x−1)k∗2Ck2
但是注意如果枚舉到第 K K K層，那麼由于這一層必須有 n n n，是以轉移方程有一些細節需要調整，而且排完所有層後會存在一些落單的節點，那麼這些節點是不能與第 K K K層的節點相連的。
示例代碼
題目傳送門
#include<cstdio>
using namespace std;
typedef long long LL;
const int tt=1e9+7;
int n,K,C[105][105],pw[10005];
LL ans,f[105][105][105];
void maken(){
for (int i=0;i<=n;i++) C[i][0]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=i;j++)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%tt;
pw[0]=1; for (int i=1;i<=n*n;i++) pw[i]=pw[i-1]*2%tt;
}
LL ksm(LL x,int y){
LL sum=1,w=x;
for (;y;y>>=1,w=w*w%tt) if (y&1) sum=sum*w%tt;
return sum%tt;
}
int main()
{
freopen("portal.in","r",stdin);
freopen("portal.out","w",stdout);
scanf("%d%d",&n,&K); maken(); f[0][1][1]=1;
for (int i=1;i<=K;i++)
for (int j=i+1;j<=n-K+i;j++)
for (int k=1;k<=j-i;k++){
LL tem=(i==K)?C[n-j+k-1][k-1]:C[n-j+k-1][k];
for (int x=1;x<=j-k-i+1;x++)
f[i][j][k]=(f[i][j][k]+f[i-1][j-k][x]*tem%tt*ksm(pw[x]+tt-1,k)%tt*pw[C[k][2]]%tt)%tt;
if (i==K) ans=(ans+f[i][j][k]*pw[k*(n-j)+C[n-j][2]]%tt)%tt;
}
printf("%lld",ans);
return 0;
}