不是那么简单的矩阵树。 题目描述 T 国有 $N$ 个城市,用若干双向道路连接。一对城市之间至多存在一条道路。 在一次洪水之后,一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况,但直到...
线性代数
CF1163E Magical Permutation 题解【线性基】【递归】【构造】
首先恭喜 xht37 喜提本场 rk1。 考场上想到线性基了不会构造…貌似还有一些别的细节 Description Kuro has just learned about permutations and he is really excited to create a new permutation typ...
洛谷 P4336 [SHOI2016]黑暗前的幻想乡 题解【矩阵树定理】【容斥】
矩阵树定理明明只是个记结论的东西对吧..(大雾 题目描述 四年一度的幻想乡大选开始了,最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡,扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪(人类...
hdu 3949 XOR 题解【线性基】【二进制】
线性基的题都好有意思啊 Problem Description XOR is a kind of bit operator, we define that as follow: for two binary base number A and B, let C=A XOR B, then for each bit of C, we can get it...
洛谷 P3265 / loj 2108 [JLOI2015]装备购买 题解【贪心】【线性基】
线性基思想入门题。 题目描述 脸哥最近在玩一款神奇的游戏,这个游戏里有 $ n$ 件装备,每件装备有 $ m$ 个属性,用向量 $ \mathbf z_i=(a_1, \ldots ,a_j, \ldots , a_m)$ 表示 $ (1 \leq i \leq n, \ ...
数列 题解【矩阵加速递推】【数学】
带关于\(n\)的高次项也可以矩阵加速。 题目描述 这是一道很简单的题。 给你两个数\(a_1,a_2\),求\(a_n\)在模\(2147439647\)下的值。 满足递推关系:\(a_n=a_{n-1}+2a_{n-2}+n^4\) 保...
洛谷 P3193 [HNOI2008]GT考试 题解【KMP】【矩阵加速】【递推】
看出来矩阵加速也没看出来KMP…… 题目描述 阿申准备报名参加 GT 考试,准考证号为\(N\)位数\(X_1,X_2…X_n(0\le X_i\le9)\),他不希望准考证号上出现不吉利的数字。 他的不吉利数学\(A_1,A...
P哥破解密码 题解【递推】【矩阵加速递推】
1e9的类似dp的东西以后都要想矩阵加速了噢。 题目背景 P哥是一个经常丢密码条的男孩子。 在ION 8102赛场上,P哥又弄丢了密码条,笔试满分的他当然知道这可是要扣5分作为...
洛谷 P2831 NOIp2016提高组 愤怒的小鸟 题解【DP】【状态压缩】【高斯消元】【枚举】
题面很长的题?不过不是很难做,精度问题坑死了…… 题目描述 Kiana最近沉迷于一款神奇的游戏无法自拔。 简单来说,这款游戏是在一个平面上进行的。 有一架...
矩阵学习笔记2 矩阵加速递推【矩阵】
在学习笔记1中的矩阵乘法公式中,我们看出,每个位置的值都是多个积之和。那么如果矩阵可以加速这样的快速幂/乘法,那么就同理可以加速加法了。因此对于那些有递推关系的式子,我们就可以用矩阵加...