洛谷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分析毒瘤 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]$ 内所有维护的矩阵的和，再乘上 $...
UVA11149 Power of Matrix
UVaLuoguVjudge分析直接暴力求的话是 $O(n^3k\log k)$ 或者 $O(n^3k)$ 的，显然过不去。可以考虑分治。令递归计算即可。注意一些比较坑的地方：输入的数会爆 int 、卡输出。代码// =================================== // author: M_sea // website: http://m-sea-blog.c...
UVA10655 Contemplation! Algebra
UVaLuoguVjudge分析做这题的时候 SB 了，竟然没推出来 QAQ考虑设 $f_n=a^n+b^n$ 。如果熟悉小学奥数的话可以得到边界为 $f_0=2,f_1=p$ 。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =======...
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子： $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
洛谷5024 保卫王国
LuoguLOJ分析动态 DP 。我们要求的是最小点覆盖，这个东西就等于权值和减去最大权独立集。那么就是差不多就是【模板】动态DP了。强制选的话，就把权值改成 $\infty$ ；强制不选的话，就把权值改成 $-\infty$ 。然后就做完了。代码// =================================== // author: M_sea // website: h...
NOIP2018简要题解
PJ标题统计按照题意模拟即可。龙虎斗枚举即可。记得开 $\texttt{long long}$ 。摆渡车设 $f[i]$ 表示前 $i$ 时刻的答案，容易得到 $\displaystyle f[i]=\min_{j\leq i-m}\{f[j]+\sum_{j<k\leq i}i-t_k\}$ 。直接前缀和优化即可得到 $50$ 分。考虑优化。可以发现 $j$ 只需要从 $i-2m+1...
SPOJ GSS3 - Can you answer these queries III
SPOJLuogu分析动态 DP 。重新定义一个矩阵乘法：假设 $C=A\times B$ ，那么 $\displaystyle C_{i,j}=\max_k\{A_{i,k}+B_{k,j}\}$ 。可以发现这个矩阵乘法仍然满足结合律。设 $f_i$ 表示以 $i$ 结尾的最大子段和，$g_i$ 表示以 $1\sim i$ 的最大子段和。那么有 $f_i=\max\{f_{i-1}+a_i...