快速幂

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;
    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 imes bmod p=a imes b-lfloor frac{ab}{p} floor 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回路的价值和对应的方案数。(nleq 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)最后的结果可以看成是(Soplus X)的结果，于是考虑全0局面对应能达到的局面。

（以下证明思路来自小伙伴喵铃@Mobius Meow（喵神太强辣！），以及下面的线代是临时学的（// //）

记(n)阶方阵(A=egin{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&1end{bmatrix})，以及(X=egin{bmatrix}x1\x2\vdots\x_nend{bmatrix})，(B=egin{bmatrix}b_1\b_2\vdots\b_nend{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}-egin{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&1end{vmatrix}=F_{n-1}-F_{n-2})

以及边界条件(F_{1}=egin{vmatrix}1end{vmatrix}=1),以及(F_2=egin{vmatrix}1&1\1&1end{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)。