【刷题笔记】[ABC281G] Farthest City

SXD-AK-IOI / 2024-10-11 / 原文

【刷题笔记】[ABC281G] Farthest City

题意

求构造一个没有重边和自环【简单联通】的无向连通图，使得$d[n]$严格大于$d[i]$，问有几种构造方案

思路

一道$DP$好题
$DP$有$2$种题型，求最优值问题，和计数问题。本题为计数问题。
因为在边权为1的最短路中

\[d[i]=d[i-1]+1 \]

所以对于一个最短路最长为$x$的连通图，最短路长度为$i,0\le i \le x$的点，个数一定大于等于$1$
多画几组样例就可以发现，可以将图进行分层。
我们将最短路长度相同的点分到一层，这一层其实就是动态规划中的一个阶段。
假设当前图的总点数为$i$,最后一层选了$j$个点，容易发现这$j$个点对答案的贡献只与上一层的点的个数有关。于是状态就出来了

\[f[i][j] \]

表示当前有$i$个点，最后一层选了$j$个点时的构造方案数。
再考虑如何计算贡献。假设最后一层有$j$个点，上一层有$k$个点。容易发现最后一层的点，每一个至多和上一层连$k$条边，至少连$1$条边。
所以每一个点于上一层有

\[C_k^1+C_k^2+...C_k^k=2^k-1 \]

种方案。而当前层有$j$个点，所以共有

\[(2^k-1)^j \]

种方案
观察样例可以发现同一层种任意两点之间连边不会影响啊最短路长度，而两点间一共有$\frac{j\times (j-1)}{2}$条边，而每条边有选与不选两种情况，因此共

\[2^{\frac{j\times (j-1)}{2}} \]

种方案
由于一共有$n$个点，一共选了$i$个点，最后一层有$j$个，而第$n$个点不能选所以$j$可以从

\[n-(i-j)-1=n-i+j-1 \]

因此有

\[C_{n-i+j-1}^j \]

种选法
最后相加求和，愉快的得到$DP$方程

\[f_{i,j}=\sum_{k = 1}^{i-j} f_{i-j,k}\times (2^k-1)^j\times 2^{\frac{j\times (j-1)}{2}} \times C_{n-i+j-1}^j \]

而答案就是

\[f_{n,1} \]

attention

1.注意当遍历到$n$层时，共有

\[C_{n-i-j}^j \]

种选法，因为第$n$个点此时可以备选。
2.有许多幂运算可以被提前预处理，处理时注意$x^0=1$
3.$\%$和$*$是同级运算符，不用加括号，从左到右取余即可，不要写括号树了

code

#include<bits/stdc++.h>
#define maxn 510
#define ll long long
using namespace std;
ll n,m;
ll c[maxn][maxn],h[maxn][maxn],f[maxn][maxn],g[maxn*maxn];
ll s[maxn][maxn];
void pre1(){
	c[1][1]=1;c[1][0]=1;
	for(int i=2;i<=n;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%m;
		}
	}
	c[0][0]=1;c[0][1]=1;
}
ll fast(ll a,ll p){
	ll s=1;
	a%=m;
	while(p){
		if(p&1)s=(s*a)%m;
		a=(a*a)%m;
		p>>=1;
	}
	return s;
}
void pre2(){
	g[0]=1;
	for(int i=1;i<=n*n;i++){
		g[i]=(g[i-1]*2)%m;
	}
}
void pre3(){
	for(int i=1;i<=n;i++){
		s[i][0]=1;
		for(int j=1;j<=n;j++){
			s[i][j]=(s[i][j-1]*((g[i]-1+m)%m))%m;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	pre1();
	pre2();
	pre3();
	//cout<<s[3][4];
	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++){
				ll cur;
				if(i==n)cur=n-i+j;
				else cur=n-i+j-1;
				f[i][j]=(f[i][j]+f[i-j][k]*c[cur][j]%m*s[k][j]%m*g[j*(j-1)/2]%m)%m;
				//f[i][j]=(f[i][j]+((f[i-j][k]*c[cur][j])%m*(s[k][j]*g[(j*(j-1))/2])%m)%m)%m;
				//cout<<f[i][j]<<' '; 
			}
		}
	}
	cout<<f[n][1];
	return 0;
}