洛谷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}$。转移时直接枚举...
AtCoder Grand Contest 003 简要题解
比赛地址Wanna go back home如果 E 和 W 仅存在一个，或者 N 和 S 仅存在一个，则一定无法回到原点，否则一定可以回到原点。代码Simplified mahjong直接扫一遍，能凑就凑即可。正确性显然。代码BBuBBBlesort!注意到使用操作 2 后不改变元素下标的奇偶性，而每个元素应该还原到的下标是已知的，因此我们可以统计出有多少个元素始末位置奇偶性不同，记为 $...
LOJ6704 健身计划
LOJ分析毒瘤 longge设 $f_i$ 表示 $n=i$ 时的答案，容易得到直接矩阵快速幂即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include &l...
洛谷3193 [HNOI2008]GT考试
LuoguBZOJ分析考虑一个 naive 的 DP。设 $f_{i,j}$ 表示前 $i$ 位匹配到不吉利数的第 $j$ 位的方案数。设 $g_{i,j}$ 表示在匹配到第 $i$ 位时加一个字符会匹配到第 $j$ 位的方案数，那么考虑如何求出 $g$。枚举每一位以及后面加的字符，然后爆跳 nxt 即可找到加字符后转移到的位置。然后注意到上面的 DP 式像矩阵乘法的形式，直接矩阵快速幂即可...
CF718C Sasha and Array
CodeforcesLuogu分析考虑怎么用矩阵求出斐波那契数列的。有为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的和，再乘上 $...