矩阵

题目链接 题意： # 有一只熊，初始在(sx,sy)处，如果当前的位置在(x,y)，那么下一秒会在((x+dx-1)%n+1,(y+dy-1)%n+1)处， dx[i] = k[i-1] + dx[i-1],dy[i]=k[i-1] + dy[i-1]，k表示的是某个点的花丛数目。

题目链接 题意： # 求f[n] = f[n-1] + f[n-2] + 1，在b(10000)进制下的最后一位数字的十进制表示。 思路： # 构造矩阵即可，M矩阵是一个3_3的矩阵，M1矩阵是一个3_1的矩阵。。很easy，就不说了。

hdu4686题目链接 题意： # An Arc of Dream is a curve defined by the following function: $$ \text{AoD}(N) = \sum_{i=0}^{N-1} a_i b_i $$where: $$ a_0 = A_0, \quad a_i = a_{i-1} A_X + A_Y $$ $$ b_0 = B_0, \quad b_i = b_{i-1} B_X + B_Y $$What is the value of \( \text{AoD}(N) \pmod{1{,}000{,}000{,}007} \)? 思路： # 看n的1E18的范围也知道是矩阵快速幂。。

uva10870题目链接 题意： # f(n) = a1f(n − 1) + a2f(n − 2) + a3f(n − 3) + . . . + adf(n − d), for n > d 给出f[1]..f[d],a[1]..a[d]，问 f[n]%m是多少。

uva10655题目链接 题意： # 给出a+b和ab的值，问a^n+b^n 思路： # 构造矩阵，手写一下很显然…

1009: [HNOI2008]GT考试 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 3127 Solved: 1926 [Submit][Status][Discuss] Description # 阿申准备报名参加GT考试，准考证号为N位数X1X2….Xn(0<=Xi<=9)，他不希望准考证号上出现不吉利的数字。 他的不吉利数学A1A2…Am(0<=Ai<=9)有M位，不出现是指X1X2…Xn中没有恰好一段等于A1A2…Am. A1和X1可以为 0

题目链接 题意： F0 = 1 , F1 = 1 , F2 = 2 , Fn = Fn-1+Fn-2 求： FFFn Mod P ( 也就是 F[ F[ F[n] ] ] % P ) 思路：原来这是适牛出的题2333. 需要注意的是p可能为1，因此n==0或者1的时候，特判要输出1%p而不是1.

题目链接 题意： Given n (1 <= n <= 1018), You should solve for g(g(g(n))) mod 109 + 7 where g(n) = 3g(n - 1) + g(n - 2) g(1) = 1 g(0) = 0 思路：找循环节。首先由于模数固定，可以暴力一下找到循环节。 得到1E9+7的循环节是222222224,222222224的循环节是183120.

题目链接 题意：A number sequence is defined as follows: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. Given A, B, and n, you are to calculate the value of f(n). 思路：矩阵加速线性递推式。 这题第一次看是2012年11月2333，当时用pascal写的

题目链接 题意：给出了一段伪代码。分析得知其实就是f[1]= a,f[2] = b,f[n]=f[n-1] * f[n-2] 思路：一眼题，和hdu4549很类似hdu4549解题报告 不同的是这道题中p不一定是质数（其实不是也无所谓啊…hdu4549只不过是因为1E9+7是指数，又用费马小定理化简了一下，这道理%phi(p)即可）

4547: Hdu5171 小奇的集合 # Time Limit: 2 Sec Memory Limit: 256 MB Submit: 263 Solved: 113 [Submit][Status][Discuss] Description # 有一个大小为n的可重集S，小奇每次操作可以加入一个数a+b(a,b均属于S)，求k次操作后它可获得的S的和的最大值。（数据保证这个值为非负数）

题目链接 题意：给出n,k，以及n个正数，把n个数放在一个集合里，进行k次操作，每次操作取最大的数和次大的数放进集合。问k次操作结束后，集合中所有数的和。 思路：假设初始时刻，次大和最大分别为a0,a1，那么得到的就是一个类斐波那契数列。初始为a0,a1,fn = fn-1 + fn

题目链接 题意：Step 1: Calculate a new NN matrix C = AB. Step 2: Calculate M = C^(N*N). Step 3: For each element x in M, calculate x % 6. All the remainders form a new matrix M’. Step 4: Calculate the sum of all the elements in M’. 思路： 水题。。就一个trick…

题意：给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值 思路： ** 把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，CA的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要快速幂求出A^k即可。**

题目链接 题意： Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak. 思路： 对k进行二分。 比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

题目链接 题意：求f[n] % 10000,f为斐波那契数。 思路：按照题目给出的公式，或者按照加速线性递推式的方法都可以。。。 因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。

找到了篇四年前空间中的旧文，也是有点感动2333. 快速求解多项递推式 # 问题描述： 已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+….. 求解 F(n)%P 分析： ＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

参考资料： 十个利用矩阵乘法解决的经典题目

http://acm.hdu.edu.cn/showproblem.php?pid=1575 题意：A为一方阵，求(A^k)73得到的矩阵的主对角线的和。 思路：矩阵快速幂。模板题。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年02月21日 星期日 10时28分33秒 4File Name :code/hdu/1575.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=12; 34const int MOD = 9973; 35struct Mat 36{ 37 int mat[N][N]; 38 void clear() 39 { 40 ms(mat,0); 41 } 42}A; 43int n,k; 44 45Mat operator * (Mat a,Mat b) 46{ 47 Mat c; 48 c.clear(); 49 for ( int i = 0 ; i < n ; i++) 50 for ( int j = 0 ; j < n ; j++) 51 for (int k = 0 ; k < n ; k++) 52 c.mat[i][j] =(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD; 53 54 return c; 55 56} 57Mat operator ^ (Mat a,int b) 58{ 59 Mat c; 60 for ( int i = 0 ; i < n ; i++) 61 for ( int j = 0 ; j < n ; j++ ) 62 c.mat[i][j]=(i==j); 63 while (b) 64 { 65 if (b&1) c = c * a; 66 b = b>>1; 67 a = a * a; 68 } 69 return c; 70} 71int main() 72{ 73 #ifndef ONLINE_JUDGE 74 freopen("code/in.txt","r",stdin); 75 #endif 76 77 int T; 78 scanf("%d",&T); 79 while (T--) 80 { 81 scanf("%d %d",&n,&k); 82 A.clear(); 83 for ( int i = 0 ; i < n ; i++) 84 for ( int j = 0 ; j < n; j ++) 85 scanf("%d",&A.mat[i][j]); 86 87 Mat res; 88 res.clear(); 89 res = A^k; 90 91 int ans = 0 ; 92 for ( int i = 0 ; i < n ;i++) ans = (ans +res.mat[i][i])%MOD; 93 94 printf("%d\n",ans); 95 96 } 97 98 99 #ifndef ONLINE_JUDGE 100 fclose(stdin); 101 #endif 102 return 0; 103}

http://codeforces.com/problemset/problem/621/E # 题意：有b组数，每组数均有n个且相同。你必须在每组选一个数，组成一个新数sum，使得sum % x == k，问方案数 % (1e9+7)。 思路：数位dp.首先考虑b不是很大的一般情况。dp[i][j]表示处理到前i个块的时候结果为j的方案数。那么转移方程就是：**dp[i][(j_10+t)%x] = dp[i-1][j]_cnt[t] ** cnt[i]表示数字i出现的个数。