矩阵乘法总结

矩阵乘法(logN)

对于一个m行n列的矩阵乘一个n行p列的矩阵，得到一个m行p列的矩阵； 一般用来优化递推； Hint: 矩阵不满足交换律；即A*B != B*A 　　矩阵乘法满足分配律: 　　 (k+l)A=kA+lA； 　　 k(A+B)=kA+kB； 　　 k(lA)=(kl)A；

注意：while(n)是非0即正，要注意判断是否为负数；或直接改成while(n>0);　　

矩阵加法： 　　结果矩阵中的第i行第j列的值，为A矩阵第i行第j列的值与B矩阵第i行第j列的数值和

　　c.m[i][j]=(a.m[i][j]+b.m[i][j])%MOD;

矩阵乘法： 　　结果矩阵中的第i行第j列的值，结果为A矩阵中第i行，与B矩阵中第j列中，每一对应的项的乘积和；

　　c.m[i][j]=(c.[i][j]+a.m[i][k]*b.m[k][j])%MOD;

数组复制：memcpy(a,c,sizeof(c));(将c复制给a)；

做题记录：

POJ-3233Codevs-3332Voj-1067 Hint: 对于这种优化递推的矩阵乘，除了要构造出矩阵外，还要注意初始矩阵的赋值；初始矩阵的值应该先递推出来；VOJ-1049 Hint:坑点很多，可以把每一个置换看成一个矩阵，那么对于k次变化，把m个置换矩阵乘起来，就得到一个m次变化的总矩阵，把原数列乘(k/m)次，然后再把还没有变换的k%m变换上就可以了，注意余数为0的情况；BZOJ2326[数学作业] Hint 将大数据按log10()优化；HDU-5171

CodeForces-551D [Gukiz and Binary Operations]

Hint:这里需要用到二进制的思想，因为二进制每一位都是独立的，所以只需要考虑 ai 每一位的情况即可；设f[i][0]为第i位是0的情况，f[i][1]为第i位是1的情况，那么

{f[i][0]=f[i][1](因为如果有这个数，这个数肯定要有一位是1)；f[i][1]=f[i][0]+f[i][1]； 设dp[i]=f[i][0]+f[i][1]；总的方案数，则 dp[i]=f[i-1][1]+f[i-1][0]+f[i-1][1]； dp[i]=dp[i-1]+f[i-2][0]+f[i-2][1]； dp[i]=dp[i-1]+dp[i-2]； 那么，这个就是Fbi数列； 因为二进制位是可以独立考虑的，那么放0或者放1的总的方案数就是 2n 种，再减去放0的方案数，就是放1的合法方案数； 放0的方案数就是上面推出来的Fbi数的第n项(因为从递推公式可以知道f[n]中一定包含至少含有1个0的情况)； 考虑到乘法原理，那么把每一项的方案数乘起来就是结果；

HH去散步 Hint 类似与Floyed，用矩阵来记录当前所有边能连接到的边，然后自乘T次后，如果还联通就说明从i至j可以经过T次到达； 这道题类似于这种方法，不过要将点边互换;

有意义的字符串