传送门：【HDU】4965 Fast Matrix Calculation 题目分析：因为比赛的时候写的太匆忙。。写的不堪入目，所以赛后重写了一次，顺便就贴一下了。 因为A*B=C，所以C^(N*N-1) = A*B*A*B*A*...*B*A*B，因为满足结合律所以变成A*( (B*A)^(N*N-2) )*B，因为中间得到的矩阵最大不超过K(K<=6)，所以可以对中间的矩阵快速幂，然

HDU 4960 Another OCD Patient 题意：给你一串数字  相邻x个数字合并成一个数字（相加）有一定代价  问  最少花费多少使得串变成回文串 思路： 读完题感觉像dp  数据范围也像  就开始想怎么表示状态  最简单的应该想到dp[i][j]表示i到j区间变成回文串的最小花费  状态想好了想做法  考虑将串分成AAAABBBBBBBCCC三段  即所有A合成一个数字

题目链接：https://cn.vjudge.net/problem/HDU-4965 思路：正常的矩阵之后得到的矩阵，在之后的矩阵乘法中就会爆掉，所以根据矩阵乘法结合律改变下形式：。是一个的矩阵，这样就可以愉快的矩阵快速幂了。 #include<bits/stdc++.h>using namespace std;typedef long long ll;const int N = 10

矩阵快速幂 肯定是这个没问题了。 一上来我就贴了模板。 可是一看矩阵最大是 1000*1000的。 结构体内 数组开不开这么大啊。 明显模板不合适了。。 然后看了看上面的条件。 发现（AB）^(N*N)  如果N 为2 的话  就是ABABABAB  结合律 A（BA）（BA）（BA）B 这样就是 BA 的快速幂 结果左乘 A 右乘 B。 并且 BA 是 10*10 的，