万年不更新的博客又开始更新了
大概是感觉基础不太扎实，放弃了打组队，寒假先刷刷书。
快速幂
int ksm(int a,int b){
int res=1;
for(;b;b>>=1,a=a*a)if(b&1)res=res*a;
return res;
}
一些特殊情况需要快速乘法（但实际上挺慢的），类似地做。
不过这里提到了另一种乘法的计算方式：
ll calc(ll a,ll b,ll p){
a%=p;b%=p;
ll c=(long double)a*b/p;
ll ans=a*b-c*p;
if(ans>=p)ans-=p;
else if(ans<0)ans+=p;
return ans;
}
利用\(a\times b\mod p=a\times b-\lfloor \frac{ab}{p}\rfloor p\)，前者让它自然溢出，同时后者我们用long double 储存18~19位保证高位的精度，刚好自带下取整。
同时（根据定义），这个结果一定在\([0,p-1]\)内，所以就得出了这样的代码。
现在考虑一个问题\(A+A^2+\dots+A_k\)怎么快速求？
每一项是个快速幂，感觉要在快速幂外面套一个什么东西
\(A^4=(A+A^2 )A^2 +(A+A^2)\)
\(A^5 =A*A^4 +(A+ A^2 +A^3 +A^4)\)
\(A^6=(A+A^2) A^4 +(A+A^2 +A^3 +A^4)\)
方便起见记要求的东西为\(S(k)\)，一边维护一个\(p(k)\)表示对应的\(A+A^2+\dots A^{2^k}\)，\(p(k)\)很好维护：
p=A;
for(;b;b>>=1){
//xx
p=p+A*p;
A=A*A;
}
接着就是if(b&1)res=res*A+p
Hamilton回路&状压dp
书上的一道例题的扩展（poj2288），定义Triangular Hamilton path的value为三个部分之和：1、所有点权值和。2、对于边\((i,j)\)，算上\(V_i V_j\)。3、对于路径上连续的三个点\((i,j,k)\)如果存在\((i,k)\)的边，再加上\(V_i V_j V_k\)。
问最大价值的Hamilton回路的价值和对应的方案数。\(n\leq 13\)
NPC问题，最大化，方案数，赶快写状压dp！：\(dp[S][p][q]\)，用\(p,q\)记录当前的点和上一个点，\(S\)表示走过的点集。
注意：1、特判\(n=1\)
2、\(13!\)需要开long long
费解的开关
https://www.acwing.com/problem/content/97/
acwing上的题给的是：一个开关棋盘，对一个位置进行操作的同时会反转上下左右（如果存在）的开关的状态，问点亮全部开关需要的最少步数。\(n\)很小
原题比较好做，注意到对于每一行来说，只能由它自己，它的上一行以及下一行影响。如果从上往下考虑，枚举第一行操作哪些位置，再根据第一行的状态（因为要全部点亮）确定第二行操作的位置，以此类推。最后check最后一行是否全亮即可。
不过在实现的时候我想到这么一个问题：一行\(n\)个开关，是否点亮一共有\(2^n\)种状态，是否操作也同样是\(2^n\)种状态，第一反应觉得这两个东西是一一对应的，于是刚开始我尝试去枚举是否点亮，发现做不下去…因为似乎没法往回推。
接着冷静一下发现确实不行…比如\(n=2\)的时候\((0,0)\)的状态不论如何操作都到不了\((1,0)\)或是\((0,1)\)。
进一步地，我们尝试考虑这么一个问题：对于一行的开关，给定任意一个初始局面，经过任意操作之后能到达的局面有多少种？
（小声bb：打表找规律，发现\(n=3k-1\)的地方答案是\(2^{n-1}\)，其余的都是\(2^n\)，嗯，怎么证明呢？）
首先任意初始局面其实无所谓，考虑一个全0的局面经过一些操作得到一个局面\(X\)，初始局面\(S\)最后的结果可以看成是\(S\oplus X\)的结果，于是考虑全0局面对应能达到的局面。
（以下证明思路来自小伙伴喵铃@Mobius Meow（喵神太强辣！），以及下面的线代是临时学的（// //）
记\(n\)阶方阵\(A=\begin{bmatrix}1&1&0&0&\cdots&0&0&0\\1&1&1&0&\cdots&0&0&0\\0&1&1&1&\cdots&0&0&0\\\vdots&\vdots&\vdots& \vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&0&\cdots&1&1&1\\0&0&0&0&\cdots&0&1&1\end{bmatrix}\)，以及\(X=\begin{bmatrix}x1\\x2\\\vdots\\x_n\end{bmatrix}\)，\(B=\begin{bmatrix}b_1\\b_2\\\vdots\\b_n\end{bmatrix}\)，其中\(X\)对应每个位置的操作，\(B\)对应最后到达的局面，则问题转化成有多少组\(B\)使得\(AX=B\)有解（对应的运算为异或）。
进一步转化成判断矩阵\(A\)是否可逆，即考虑矩阵的秩。
注意到\(A\)的秩\(r(A)\)至少是\(n-1\)：从对应的意义考虑，从左到右操作，用第\(i\)个位置的操作来校准\(i-1\)位置上的灯，则至少可以让前\(n-1\)盏灯变成我们需要的状态。
于是答案要么是\(2^n\)要么是\(2^{n-1}\)，这样的话就直接计算\(A\)的行列式好了。记\(n\)阶方阵\(A\)对应的行列式为\(F_n\)，则考虑对第一列进行Laplace展开：
\(F_{n}=F_{n-1}-\begin{vmatrix}1&0&0&\cdots&0&0&0\\1&1&1&\cdots&0&0&0\\\vdots&\vdots& \vdots&\ddots&\vdots&\vdots&\vdots\\0&0&0&\cdots&1&1&1\\0&0&0&\cdots&0&1&1\end{vmatrix}=F_{n-1}-F_{n-2}\)
以及边界条件\(F_{1}=\begin{vmatrix}1\end{vmatrix}=1\),以及\(F_2=\begin{vmatrix}1&1\\1&1\end{vmatrix}=0\)，得出\(F_n\)的前8项分别为：\(1,0,-1,-1,0,1,1,0\)，以及注意到递推式\(F_n=F_{n-1}-F_{n-2}\)对应的特征方程\(x^2-x+1=0\)判别式\(\Delta=1-4=-3<0\)，于是我们可以直接推定\(F_n\)有周期6，进一步得出对于\(n=3k-1\)的\(n\)有\(F_n=0\)，即这些\(n\)对应的矩阵\(A\)满秩，对应的方案数是\(2^{n-1}\)，对于其他\(n\)则是\(2^n\)。