洛谷 P12415 「YLLOI-R1-T4」枫
原题
思路
根据题意，很显然我们可以一行一行地考虑计算答案。注意到，当第 $ i $ 行确定后，其对后面行的答案并不会产生影响，也就是无后效性，于是考虑 $ dp $ 计算答案。
定义状态：$ f_{i,j} $ ，表示前 $ i-1 $ 行，填了 $ j $ 个节点的方案数；
状态转移：考虑第 $ i $ 行选 $ k $ 个节点的方案数。
- 根据题面中的条件二，有从 $ m $ 个选择 $ k $ 个的方案数： $ C_{m}^{k} $ ;
- 根据题面中的条件三， $ k $ 个点中的任意一点都可以挂在前面已经确定的 $ j $ 个父亲上，于是方案数为 $ \displaystyle \prod_{i=1}^{k}j \rightarrow j^{k} $ 。
于是有状态转移方程：$ f_{i,j+k}= f_{i,j+k}+f_{i-1,j} \times C_{m}^{k} \times j^{k} $ ;
初始化：$ f_{1,1}=m $ 。
答案统计：$ ans= \displaystyle \sum_{i=1}^{n} \sum_{j=0}^{n*m} f_{i,j} $ 。
计算优化
预处理组合数和 $ j^{k} $ ，最终时间复杂度为 $ O(n^{2} \cdot m^{2}) $ 。
code
code
#include <bits/stdc++.h>
#define i8 __int128
#define int long long
#define ull unsigned long long
#define fuck inline
#define lb long double
using namespace std;
// typedef long long ll;
const int N=100+5,mod=1e9+7,mod2=1e9+3342522;
const int INF=1e9+7;
const int inf=LONG_LONG_MAX/4;
// const int mod1=469762049,mod2=998244353,mod3=1004535809;
// const int G=3,Gi=332748118;
// const int M=mod1*mod2;
fuck int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-'0');c=getchar();}return x*f;
}
fuck void write(int x)
{if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}
int fac[N],ifac[N],inv[N];
fuck void pre()
{fac[0]=1,ifac[0]=1,inv[1]=1;for(int i=1;i<=N-5;i++)fac[i]=fac[i-1]*i%mod;for(int i=2;i<=N-5;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;for(int i=1;i<=N-5;i++)ifac[i]=ifac[i-1]*inv[i]%mod;
}
fuck int C(int a,int b)
{if(a<b||b<0)return 0;else if(a==b)return 1;else return fac[a]%mod*ifac[b]%mod*ifac[a-b]%mod;
}
fuck int ksm(int a,int b)
{int res=1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
int zs[N*N][N];
fuck void pre2()
{for(int i=1;i<=N*N-5;i++)for(int j=0;j<=N-5;j++)zs[i][j]=ksm(i,j);
}
int n,m;
int f[N][N*N];
fuck void solve()
{pre();pre2();cin>>n>>m;f[1][1]=m;for(int i=2;i<=n;i++)for(int j=1;j<=(i-1)*m;j++)for(int k=0;k<=m;k++)f[i][j+k]=(f[i][j+k]+f[i-1][j]%mod*C(m,k)%mod*zs[j][k]%mod)%mod;int ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=i*m;j++)ans=(ans+f[i][j])%mod;cout<<ans<<endl;
}
signed main()
{ solve(); return 0;
}
// 6666 66666 666666
// 6 6 6 6 6
// 6 6 6666 6
// 6 6 6 6 6
// 6666 6 6 6666666完结收工！！！！！
个人主页
看完点赞，养成习惯
\(\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\Downarrow\)