2022.9 做题记录

发表于 2022-09-27 分类于做题记录

P3205 [HNOI2010] 合唱队

$f_{l,r,0}$ 表示区间 $[l,r]$ 内为理想队列且最后一个人由左边进入的方案数．

$f_{l,r,1}$ 表示区间 $[l,r]$ 内为理想队列且最后一个人由右边进入的方案数．

令 $f_{x,x,0}=1$ ， $a_i$ 表示原序列的第 $i$ 个元素．

f_{l,r,0}=[a_l<a_{l+1}]f_{l+1,r,0}+[a_l<a_{r}]f_{l+1,r,1}

f_{l,r,1}=[a_l<a_r]f_{l,r-1,0}+[a_{r-1}<a_r]f_{l,r-1,1}

$f_{u,v,k}$ 表示图中存在一条 $u\rightarrow v$ 的路径，使得路径长为 $2^k$ ．

转移考虑 floyd 传递闭包的过程，枚举断点 $p$ ，如果 $f_{u,p,k-1}$ 和 $f_{p,v,k-1}$ 均为真，则 $f_{u,v,k}$ 为真．

每次转移成功都在图中连一条 $u\rightarrow v$ 的边，最后在图上求 $1\rightarrow n$ 的最短路即可．

注意到题目中给的递推式均为常系数齐次线性递推，考虑矩阵快速幂．

记第 $1$ 个递推式对应的转移矩阵为 $A$ ，第 $2$ 个递推式对应的转移矩阵为 $B$ ，初始矩阵为 $S$ ．

容易得到:

S= \begin{pmatrix} 1 \\ 1 \end{pmatrix} , A= \begin{pmatrix} a & 0\\ b & 1 \end{pmatrix} , B= \begin{pmatrix} c & 0\\ d & 1 \end{pmatrix}

最后答案矩阵 $T$ 由下式计算:

T=S(A^{m-1}B)^{n-1}A^{m-1}

$T_{1,1}$ 即为答案．

注意到 $n,m$ 较大，我们有费马小定理:

x^{p-1}\equiv 1\ (\bmod\ p)

在本题中 $p=10^9+7$ ．

读入时将 $n,m$ 模 $p-1$ 即可．

注意对于转移矩阵，当 $a=1$ 或 $c=1$ 时，费马小定理不适用，应对指数模 $p$ ．

钦定根为 $1$ ．

令 $V_x$ 表示编号为 $x$ 的节点的点权， $C_u$ 表示 $u$ 的儿子所构成的集合， $F_u$ 表示节点 $u$ 的父亲．

设 $f_{u,k}$ 表示在以 $u$ 为根的子树中深度不超过 $k$ 的节点权值和， $g_{u,k}$ 表示在树中与 $u$ 的距离不超过 $k$ 的节点权值和．

容易得出 $f$ 的转移:

f_{u,k}=V_u+\sum_{v\in C_u}f_{v,k-1}

考虑 $g$ 的转移．对于 $1$ 个点 $u$ ， $g_{u,k}$ 由 $2$ 部分组成:

我们可以得出 $g_{u,k}$ 的转移:

g_{u,k}=f_{u,k}+g_{F_u,k-1}-f_{u,k-2}

其中 $f_{u,k}$ 为第 $1$ 部分， $g_{F_u,k-1}-f_{u,k-2}$ 为第 $2$ 部分．

约定 $\texttt{W}$ 为第 $1$ 种字符， $\texttt{I}$ 为第 $2$ 种字符， $\texttt{N}$ 为第 $3$ 种字符， $\texttt{G}$ 为第 $4$ 种字符．

令 $c_{i,j,k}$ 表示第 $i$ 种字符可以转变成的串的第 $k$ 个字符，其中 $i\in[1,4],k\in[1,2]$ ．

设 $f_{l,r,x}$ 表示目标串在 $l\sim r$ 内能够由单个第 $x$ 种字符转化而成．

转移时枚举转移断点 $k$ ，字符种类 $i$ ，要替换的字符串 $j$ ．转移如下:

f_{l,r,i}=f_{l,k,r_{i,j,0}}\land f_{k+1,r,r_{i,j,1}}

令 $i$ 号卡牌上的数字为 $c_i$ ，卡牌数目为 $m$ ．

设 $f_{i,j}$ 表示有 $i$ 人参加游戏，且 $j$ 号玩家胜出的概率．显然有 $f_{1,1}=1$ ．

考虑转移， $i$ 人参加游戏的状态可由 $i-1$ 人参加游戏的状态转移而来．

记 $i$ 人参加游戏时的 $j$ 号玩家在 $i-1$ 人参加游戏且该轮游戏中庄家抽出的卡牌编号为 $k$ 时的编号为 $x_{i,j,k}$ ．

x_{i,j,k}=j-c_{k}\bmod i

要注意的是，当 $j=c_{k}\bmod i$ 时， $j$ 号玩家被淘汰，此时不应进行转移．

综上，我们有转移:

f_{i,j}=\frac{1}{m}\sum_{k=1}^{m}[j\not =c_{k}\bmod i]f_{i-1,x_{i,j,k}}

当然，我们可以令 $f_{x,0}=0$ ，转移可简化为:

f_{i,j}=\frac{1}{m}\sum_{k=1}^{m}f_{i-1,x_{i,j,k}}

每次对整棵树进行查询，考虑使用并查集进行维护．

考虑修改操作，每次修改将 $v$ 接到 $u$ 下． $u$ 作为新树的根，填入数字时只能填 $0$ ．

令 $s_u$ 代表以 u 为根的树的大小，修改时 $s_u$ 直接加上 $s_v$ 即可．

设 $a_u$ 为以 $u$ 为根的树中的填数方案数．修改后 $v$ 的子树内共有 $s_v$ 个节点，可以填入 $s_u-1$ 个数字，方案数为 $\tbinom{s_u-1}{s_v}$ ．根据乘法原理，每次修改时我们有：

a_u=a_u\times a_v\times\dbinom{s_u-1}{s_v}