UOJ551 【UNR #4】校园闲逛
UOJ 分析 设 $f_{i ,j, w}$ 为从 $i$ 走到 $j$、权值和为 $w$ 的方案数，$g_{i, j, w}$ 表示连接 $i,j$ 的权值为 $k$ 的边数。 那么有 可以证明 $I-G$ 一定是可逆的。于是我们只需要求一个每个元素都是一个多项式的矩阵的逆，和普通矩阵求逆类似地做即可。 然而这题还卡常，需要精细地实现来减少 NTT 的次数，最好把预处理原根、取模优化、寻...
标签 矩阵 下的文章
- 首页
- 矩阵
CF107D Crime Management
Codeforces Luogu 分析 不难想到 DP。设 $dp_{i,a_1,a_2,\cdots}$ 表示前 $i$ 个字符，字符 $c_j$ 的出现次数模 $m_j$ 等于 $a_j$ 时的方案数。转移枚举在后面填的字符即可。 因为 $\prod m_i\leq 123$，所以后面的状态至多只有 $123$ 种，因此直接矩阵快速幂即可。 实现时需要把后面的状态压成一个数。我的做法是压...
洛谷6772 [NOI2020]美食家
Luogu LOJ 分析 如果见得多的话，从 “恰好第 $T$ 天回到城市 $1$”、$n\leq 50$、$w_i\leq 5$ 和 $T\leq 10^9$ 中不难知道本题要用矩阵快速幂。 这类问题是这样的：边有边权，求从 $i$ 出发经过恰好 $k$ 条边走到 $j$ 的最长路。 对这种题可以想到 DP。设 $dp_{k,i,j}$ 表示从 $i$ 出发经过恰好 $k$ 条边走到 $...
洛谷6630 [ZJOI2020]传统艺能
Luogu LOJ 分析 因为期望具有线性性，所以可以对每个节点计算它在 $k$ 次操作后有标记的概率，全部加起来即为答案。 考虑 DP。设 $f_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后有标记的概率，$g_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后某个祖先有标记的概率，$h_{i,j}$ 表示 $i$ 节点在 $j$ 次操作后自己和祖先都没有标记的概率。 转移需要再求...
CF1067D Computer Game
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
洛谷5364 [SNOI2017]礼物
Luogu LOJ 分析 设 $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]组合数问题
Luogu LOJ 分析 考虑要求的东西的组合意义，为从 $nk$ 个物品中选出 $t$ 个物品的方案数，其中 $t\bmod k=r$。 考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，选出的物品数量模 $k$ 为 $j$ 时的方案数。显然有转移 直接矩阵快速幂即可。 需要注意的是 $k=1$ 时转移矩阵是 $[2]$。 代码 // ====================...
CF1286D LCC
Codeforces Luogu 分析 容易发现最早碰撞的一定是相邻的两个球。 我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。 这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每...
洛谷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}$。转移时直...
LOJ6704 健身计划
LOJ 分析 设 $f_i$ 表示 $n=i$ 时的答案，容易得到 直接矩阵快速幂即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <a...