矩阵快速幂

OI
矩阵快速幂.md

前置技能

矩阵乘法

复杂度为$O(n^3)$,有复杂度稍低的分治写法,不过意义不大(毕竟你的矩阵这么小)

$A,B$是两个矩阵,其中$A$是$m\times n$的矩阵,$B$是$x\times y$的矩阵

当且仅当$n=x$时$A\cdot B$有意义。

状态压缩学习笔记 (1)

OI

[COGS 1516] 棋盘上的车

题目描述

原题地址:COGS

思路一

乘法原理水过,计算$n!$即可,复杂度$O(n)$

思路二

DP方程

每次放置一枚棋子,一行一行放,可以用一个二进制数表示状态,如$(0010011)_2$表示第一、二、五列已放棋子。

设$f(n)$是放置$n$枚棋子的方案数,可以知道,$f((0010011)_2)=f((0000011)_2)+f((0010001)_2)+f((0010010)_2)$,类似地,我们可以推出方程:

[COGS 172][IOI 2000] 回文词

OI

题目描述

原题地址:COGS

思路

本来没有什么想法,搜了一下题解之后发现一个很妙的方法,将字符串正反各读一遍,然后求最长公共子序列的长度,最后再用总长度减一下就可以了