Pro3996 勇者 题解
$\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
|