Gravatar
yrtiop
积分:2101
提交:309 / 808

$\mathrm {Subtask}1: n\le 5$。

直接 $\mathcal O(n^m)$ 爆搜,暴力判强连通即可。

$\mathrm{Subtask} 2: n\le 15$。

这个我没有写,不知道对不对。

考虑状压 dp。

思考强连通图的形成过程,一定是从 $1$ 所在的强连通分量中的某个点出发,走到某些还不在这个强连通分量的点,然后走回 $1$ 所在的强连通分量中的某个点。

并且,我们并不关心起点终点具体是那个点。

据此,设 $f(S,t)$ 表示 $t$ 秒后 $1$ 所在的强连通分量为 $S$ 的方案数。

转移大概就是设 $g(S,t)$ 表示经过 $t$ 秒经过了 $S$ 中这些点的方案数,然后转移做一个二维的合并:$f(S_1,t_1)\times g(S_2,t_2)\to f(S_1\cup S_2, t_1+t_2)[S_1\cap S_2 = \emptyset]$。

复杂度 $\mathcal O(3^n \mathrm{poly}(n))$。

$\mathrm{Subtask 3}:n\le 300$。

考虑优化状压 dp。两种方法优化到正解:重构 dp 状态,分步转移。两者殊途同归。

因为我们并不关心 $1$ 所在的强连通分量具体是啥,所以设 $f(i,j,k)$ 表示 $i$ 次操作后 $1$ 所在的强连通分量大小为 $j$,目前往外扩展了 $k$ 个新点的方案数。

初始状态 $f(0,1,0)=1$。三种转移,分别对应走回 $1$ 所在的强连通分量,走一个新点,走到一个还在构建的点。

$$f(i,j,k)\times j\to f(i+1,j+k,0)$$

$$f(i,j,k)\times (n-j-k)\to f(i+1,j,k+1)$$

$$f(i,j,k)\times k\to f(i+1,j,k)$$

答案就是 $f(m,n,0)$。

注意!!!这里有个大坑点!!!

模数是 $10^9 + 7$ 而不是 $998244353$。有人缺省源里 $\mathrm{mod}=998244353$ 调了一年。




题目3996  勇者 AAAAAAAAAA      7      评论
2024-07-04 14:32:34