[NOI2023] 桂花树

月心绽放的末日 / 2023-07-31 / 原文

\(k=0\)

考试时脑抽，现在想一想感觉挺简单的。

从小到大依次加点，那么题目的条件等价于每次可以把点加在一条边中间，或者加入一个叶子，并且这两种方式都会导致下一个点加入时可选的方案加二。

把方案数乘起来就好了。

\(k>0\)

需要一点观察。

除了上述两种加点的方式，还存在一种方式是，选择一个节点 \(x<y\le x+k\)，把 \(y\) 加在一条边中，\(x\) 作为 \(y\) 的儿子。

容易证明这样可以不重不漏地搜索所有的合法树。

那么状压记录一下 \([x+1,x+k]\) 这段区间有多少点已经被加入树里面，转移分三种讨论就行了。

复杂度 \(O(m2^kk)\)

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[2][(1<<12)];
void solve()
{
	int n,m,k;
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<n;i++)
	{
		int x;
		scanf("%d",&x);
	}
	int U=(1<<k)-1;
	for(int c=0;c<=1;c++)
	for(int i=0;i<=U;i++)
	dp[c][i]=0;
	int cur=0;
	dp[0][0]=1;
	for(int p=1;p<=m;p++)
	{
		int nxt=(cur^1);
		for(int i=0;i<=U;i++)if(dp[cur][i])
		{
			if(i&1)
			{
				dp[nxt][i>>1]=(dp[nxt][i>>1]+dp[cur][i])%mod;
				dp[cur][i]=0;
				continue;
			}
			int s=n+p-1;
			for(int j=0;j<k;j++)if((i>>j)&1)s++;
			dp[nxt][i>>1]=(dp[nxt][i>>1]+1ll*dp[cur][i]*(2*s-1)%mod)%mod;
			for(int j=1;j<=k;j++)if((i>>j)%2==0)
			dp[nxt][(i|(1<<j))>>1]=(dp[nxt][(i|(1<<j))>>1]+1ll*dp[cur][i]*(s-1)%mod)%mod;
			dp[cur][i]=0;
		}
		cur=nxt;
	}
	printf("%d\n",dp[cur][0]);
}
int main()
{
	int tp,T;
	cin>>tp>>T;
	while(T--)
	{
		solve();
	}
	return 0;
}