题目链接

题意：

有一只熊，初始在(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 following function:

where a 0 = A0 a i = a i-1_AX+AY b 0 = B0 b i = b i-1_BX+BY What is the value of AoD(N) modulo 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

思路：

构造矩阵,手写一下很显然…

转移矩阵M=[0 , 1]

[-q,p ]

初始矩阵M1=[p           ]

[p^2-2*q]

快速幂即可。

有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。

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次操作结束后，集合中所有数的和。

题目链接

题意：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 …

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出现的个数。