洛谷5772 [JSOI2016]位运算
LuoguLOJBZOJ分析首先我们可以将 $n$ 个数互不相同且都小于 $R$ 的条件转化为 $R=A_0>A_1>A_2>\cdots>A_n$。考虑一个 DP。设 $dp_{i,S}$ 为前 $i$ 位大小状态为 $S$ 的方案数，其中 $S$ 的第 $i$ 位为 $0$ 表示 $A_i >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]$ 内所有维护的矩阵的和，再乘上 $...
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...