게스트 7차전 I-Valuable Forests prufer 시퀀스 + DP

전송문

제목:

뿌리 없는 나무의 값을 모든 점의 도수의 제곱과로 정의하고, 표시된 n개의 점으로 이루어진 모든 숲의 값의 합을 구한다.
T ≤ 5000 , N ≤ 5000 T\leq 5000,N\leq 5000 T≤5000,N≤5000

Solution:

시합할 때 뇌졸중, 시험 끝나고 5분 후에...
prufer 서열의 결론을 통해 알 수 있듯이 n개의 점에 대한 뿌리 없는 나무는 n-3 n^ {n-2} nn-3 2개의 다른 나무를 형성할 수 있다. 우리는 그의 값이 st nst 라고 기억한다.nstn, 그럼 n개의 점의 숲에 대한 개수 fn fn fn, 우리는 DP식을 구할 수 있다.
f ( n ) = ∑ i = 0 n − 1 C n − 1 i f ( n − i − 1 ) ∗ s t ( i + 1 ) f(n)=\sum_{i=0}^{n-1}C_{n-1}^if(n-i-1)*st(i+1) f(n)=∑i=0n−1​Cn−1i​f(n−i−1)∗st(i+1)
n번째 점을 넣을 때 i개의 점을 선택하여 그와 나무를 형성한다고 볼 수 있다.
이어서 우리는 n개의 점으로 형성할 수 있는 모든 뿌리 없는 나무의 권한을 An A 로 정의한다n An, DP 스타일 추가 가능:
A ( n ) = ∑ i = 1 n ∑ d = 1 n − 1 d 2 C n − 2 d − 1 ∗ ( n − 1 ) ( n − 2 − d + 1 ) A(n)=\sum_{i=1}^n\sum_{d=1}^{n-1}d^2C_{n-2}^{d-1}*(n-1)^{(n-2-d+1)} A(n)=∑i=1n​∑d=1n−1​d2Cn−2d−1​∗(n−1)(n−2−d+1)
여기서 우리는 각 점 i를 매거하고 이 점의 도수 d를 매거한다.prufer 서열의 성질에 따라 첫 번째 점도수가 d인 공헌은 d2d^2d2와 서열에 있고 d-1개만 있는 방안의 적수로 볼 수 있다.
여기 i가 쓸모가 없다는 것을 알아차렸기 때문에 스타일은 다음과 같이 바꿀 수 있습니다.
A ( n ) = n ∑ d = 1 n − 1 d 2 C n − 2 d − 1 ∗ ( n − 1 ) ( n − 2 − d + 1 ) A(n)=n\sum_{d=1}^{n-1}d^2C_{n-2}^{d-1}*(n-1)^{(n-2-d+1)}A(n)=n∑d=1n-3d2Cn-3d-1∗(n-1)(n-2-3-d+1)(경기할 때 발견하지 못했는데... 한나절 동안 어떻게 간소화할까 생각했다)
마지막으로 우리는 n개의 점으로 이루어진 삼림의 권치와 Fn F 를 가정한다n Fn, fn fn fn 방법은 우리가 n번째 점을 추가할 때마다 i개의 점을 선택하여 그와 나무를 형성하면 DP식을 얻을 수 있다.
F ( n ) = ∑ i = 0 n − 1 C N − 1 i ∗ ( s t ( i + 1 ) ∗ F ( n − i − 1 ) + f ( n − i − 1 ) ∗ A ( i + 1 ) ) F(n)=\sum_{i=0}^{n-1}C_{N-1}^i*(st(i+1)*F(n-i-1)+f(n-i-1)*A(i+1)) F(n)=∑i=0n−1​CN−1i​∗(st(i+1)∗F(n−i−1)+f(n−i−1)∗A(i+1))
뒤에 있는 덩굴식의 의미를 설명해 보자. i개점과 n개점을 선택하여 i+1개의 점을 가진 나무를 형성하고 이에 대응하여 다른 점은 f(n-i-1) 중의 숲을 형성할 수 있으며 각 형성 방식에 대해 A(i+1)의 가치를 기여할 수 있기 때문에 그들은 서로 곱하고 앞의 식이 이치에 맞다.
이렇게 하면 우리가 F(n)를 미리 처리하면 O(1)로 답을 찾을 수 있다.

코드:

#include
#include
using namespace std;
int n,num[100010];
int a[100010];
int C[5010][5010],A[5010],F[5010],f[5010];
int st[5010];
int T,mod;
int fast_pow(int x,int a)
{
	int ans=1;
	for (;a;x=1ll*x*x%mod,a>>=1)
		if (a&1) ans=1ll*ans*x%mod;
	return ans;
}
int main()
{
	scanf("%d%d",&T,&mod);
	C[0][0]=1;
	for (int i=1;i<=5000;i++)
	{
		C[0][i]=1;
		for (int j=1;j<=i;j++)
			C[j][i]=(1ll*C[j][i-1]+C[j-1][i-1])%mod;
	}
	st[0]=st[1]=1;
	for (int N=1;N<=5000;N++)
	{
		for (int d=1;d<=N-1;d++)
		{
			A[N]=(1ll*d*d*C[d-1][N-2]%mod*fast_pow(N-1,N-2-d+1)+A[N])%mod; 
		}
		A[N]=1ll*N*A[N]%mod;
		if (N>1) st[N]=fast_pow(N,N-2);
	}
	f[0]=1;f[1]=1;
	for (int i=2;i<=5000;i++)
	{
		for (int j=0;j