CF107D Crime Management
CodeforcesLuogu分析不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。实现时需要把后面的状态压成一个数。我的做法是压成 $\B...
标签 矩阵 下的文章
- 首页
- 矩阵
洛谷6772 [NOI2020]美食家
LuoguLOJ分析如果见得多的话，从 “恰好第 $T$ 天回到城市 $1$”、$n\leq 50$、$w_i\leq 5$ 和 $T\leq 10^9$ 中不难知道本题要用矩阵快速幂。这类问题是这样的：边有边权，求从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路。对这种题可以想到 DP。设 $dp_{k,i,j}$ 表示从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长...
洛谷6630 [ZJOI2020]传统艺能
LuoguLOJ分析因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。转移需要再求出 $5$...
CF1067D Computer Game
CodeforcesLuogu分析显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移于是只要快速找到决策点改变的位置即可。一个想法是...
洛谷6190 [NOI Online #1 入门组]魔法
Luogu分析设 $dp_{i,j,k}$ 表示用了 $k$ 次魔法从 $i$ 走到 $j$ 的最小费用。显然有转移足够熟练的话可以看出是一个广义矩阵乘法（将 $+$ 改为 $\min$，将 $\times$ 改为 $+$，仍然满足结合律）的形式，预处理 $dp_{i,j,1}$ 后矩阵快速幂即可。预处理 $dp_{i,j,1}$ 可以先 Floyd 预处理出两两之间的最短路，然后枚举哪条边...
洛谷5364 [SNOI2017]礼物
LuoguLOJ分析设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理可能需要特判 $n\leq 2$ 的情况。代码// ========...
洛谷3746 [六省联考2017]组合数问题
LuoguLOJ分析考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移直接矩阵快速幂即可。需要注意的是 $k=1$ 时转移矩阵是 $[2]$。代码// =============================...
CF1286D LCC
CodeforcesLuogu分析容易发现最早碰撞的一定是相邻的两个球。我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每次相当于修...
洛谷4007 小 Y 和恐怖的奴隶主
LuoguLOJ分析看到数据范围容易想到矩阵快速幂，因此可以考虑 DP。设 $dp_{i,a,b,c}$ 表示前 $i$ 次攻击，场上有 $a$ 个一血、$b$ 个二血、$c$ 个三血的概率。转移稍微讨论一下即可。为了求答案，再设一个 $f_i$ 表示前 $i$ 次攻击对 Boss 的期望伤害，从所有 $dp_{i,a,b,c}$ 由 $\frac{1}{a+b+c+1}$ 的概率转移过来。...
洛谷5772 [JSOI2016]位运算
Luogu分析先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直接枚举...