[[https://ac.nowcoder.com/acm/contest/11255|比赛链接]]
====== 补题情况 =====
^ 题目 ^ 蒋贤蒙 ^ 王赵安 ^ 王智彪 ^
| A | 0 | 0 | 0 |
| B | 2 | 0 | 2 |
| C | 2 | 0 | 1 |
| D | 2 | 1 | 0 |
| E | 2 | 0 | 1 |
| F | 2 | 0 | 2 |
| G | 2 | 0 | 2 |
| H | 0 | 1 | 2 |
| I | 2 | 0 | 2 |
| J | 2 | 0 | 2 |
====== 题解 ======
===== D. Rebuild Tree =====
==== 题意 ====
给定一棵树,要求删除 $k$ 条边再补上 $k$ 条边,使得新图仍然是一棵树,问方案数。
==== 题解 ====
首先删除 $k$ 条边得到 $k+1$ 个连通块,设第 $i$ 个连通块有 $s_i$ 个点。
固定 $(s_1,s_2\cdots s_{k+1})$,将每个连通块缩点后构造 $\text{prufer}$ 序列。设第 $i$ 个连通块在新图中得度数为 $d_i$,知每个生成树的贡献为
$$
\prod_{i=1}^{k+1}s_i^{d_i}
$$
设 $p_i$ 表示第 $i$ 个连通块在 $\text{prufer}$ 序列中出现的次数,根据 $\text{prufer}$ 序列性质,知 $d_i=p_i+1$,于是有
$$
\prod_{i=1}^{k+1}s_i^{d_i}=
\left(\prod_{i=1}^{k+1}s_i\right)\left(\prod_{i=1}^{k+1}s_i^{p_i}\right)
$$
考虑 $\prod_{i=1}^{k+1}s_i^{p_i}$ 在 $\text{prufer}$ 序列中的实际意义。
不难发现设 $\text{prufer}$ 序列的权值为每个元素 $a_i$ 按权值 $s_{a_i}$ 相乘之积,则所有 $\prod_{i=1}^{k+1}s_i^{p_i}$ 之和等价于所有 $\text{prufer}$ 序列的权值之和。
不难发现,所有 $\text{prufer}$ 序列的权值之和(固定其他位置,枚举单个位置的变化)等于
$$
\left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=n^{k-1}
$$
于是对固定 $(s_1,s_2\cdots s_{k+1})$,总贡献为
$$
\left(\prod_{i=1}^{k+1}s_i\right)\sum_{Tree(k+1)}\left(\prod_{i=1}^{k+1}s_i^{p_i}\right)=\left(\prod_{i=1}^{k+1}s_i\right)\left(\sum_{i=1}^{k+1} s_i\right)^{k-1}=\left(\prod_{i=1}^{k+1}s_i\right)n^{k-1}
$$
接下来考虑 $(s_1,s_2\cdots s_{k+1})$ 不固定时产生的总贡献。
不难发现 $\prod_{i=1}^{k+1}s_i$ 等于连通块的大小之积,这可以转化为在每个连通块中选一个点的方案数。
于是设 $\text{dp}(u,k,0/1)$ 表示以 $u$ 为子树已经割 $k$ 条边,$0/1$ 表示 $u$ 所在的连通块是否已经选择代表节点的方案数。
进行树形 $\text{dp}$ 转移,枚举是否割断 $u$ 与 $v\in \text{son}(u)$ 的连边的贡献,注意如果 $v$ 所在的连通块没有代表节点,则 $u\to v$ 一定不可割。
时间复杂度 $O(nk)$。
const int MAXN=5e4+5,MAXK=105,mod=998244353;
struct Edge{
int to,next;
}edge[MAXN<<1];
int head[MAXN],edge_cnt;
void Insert(int u,int v){
edge[++edge_cnt]=Edge{v,head[u]};
head[u]=edge_cnt;
}
int quick_pow(int a,int k){
int ans=1;
while(k){
if(k&1)ans=1LL*ans*a%mod;
a=1LL*a*a%mod;
k>>=1;
}
return ans;
}
void add(int &x,LL y){
x=(x+y)%mod;
}
int sz[MAXN],dp[MAXN][MAXK][2],temp[MAXK][2];
void dfs(int u,int fa){
sz[u]=1;
dp[u][0][0]=dp[u][0][1]=1;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to;
if(v==fa)continue;
dfs(v,u);
_for(j,0,min(sz[u]+sz[v],MAXK))
temp[j][0]=temp[j][1]=0;
_for(j,0,min(sz[u],MAXK))_for(k,0,min(sz[v],MAXK)){
if(j+k
===== G. Product =====
==== 题意 ====
给定 $n,k,D$,求
$$
\sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)}
$$
==== 题解 ====
不妨设 $b_i=a_i+k$
$$
\sum_{\sum a_i=D,a_i\ge 0}\frac {D!}{\prod_{i=1}^n (a_i+k)}=\frac {D!}{(D+nk)!}\sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i}
$$
不难发现,式子右半部分的组合意义是由元素 $1\sim n$ 构成的长度为 $D+nk$ 的排列个数,其中每个元素出现次数不小于 $k$。
不妨考虑容斥,设 $\text{dp}(i,j)$ 表示由元素 $1\sim i$ 构成的长度为 $j$ 的排列个数,其中每个元素出现次数小于 $k$,不难得到状态转移
$$
\text{dp}(i,j)=\sum_{v=0}^{\min(j,k)}{j\choose v}\text{dp}(i-1,j-v)
$$
同时有公式 $n$ 种元素出现次数无限制时构成的长度为 $k$ 的排列个数为 $n^k$,于是有
$$
\sum_{\sum b_i=D+nk,b_i\ge k}\frac {(D+nk)!}{\prod_{i=1}^n b_i}=\sum_{i=0}^n (-1)^n\sum_{j=0}^{ik}{D+nk\choose j}\text{dp}(i,j)(n-i)^{D+nk-j}
$$
总时间复杂度 $O\left(n^2k^2\right)$。
const int MAXN=55,MAXV=MAXN*MAXN,mod=998244353;
int quick_pow(int a,int k){
int ans=1;
while(k){
if(k&1)ans=1LL*ans*a%mod;
a=1LL*a*a%mod;
k>>=1;
}
return ans;
}
int frac[MAXV],invf[MAXV],down[MAXV];
int C(int n,int m){
return 1LL*frac[n]*invf[m]%mod*invf[n-m]%mod;
}
int C2(int n){
return 1LL*down[n]*invf[n]%mod;
}
int dp[MAXN][MAXV];
int main(){
int n=read_int(),k=read_int(),D=read_int();
//pre
frac[0]=1;
_for(i,1,MAXV)frac[i]=1LL*frac[i-1]*i%mod;
invf[MAXV-1]=quick_pow(frac[MAXV-1],mod-2);
for(int i=MAXV-1;i;i--)
invf[i-1]=1LL*invf[i]*i%mod;
down[0]=1;
_for(i,0,n*k)
down[i+1]=1LL*down[i]*(D+n*k-i)%mod;
//main
LL ans=quick_pow(n,D+n*k);
dp[0][0]=1;
_rep(i,1,n){
_for(j,0,i*k){
_for(v,0,k){
if(j>=v)
dp[i][j]=(dp[i][j]+1LL*dp[i-1][j-v]*C(j,v))%mod;
}
int d=1LL*dp[i][j]*C(n,i)%mod*C2(j)%mod*quick_pow(n-i,D+n*k-j)%mod;
if(i&1)
ans=(ans+mod-d)%mod;
else
ans=(ans+d)%mod;
}
}
int t=1;
_rep(i,D+1,D+n*k)
t=1LL*t*i%mod;
ans=ans*quick_pow(t,mod-2)%mod;
enter(ans);
return 0;
}