第8讲二分和构造矩阵-东北林业大学.ppt

ACM程序设计 东北林业大学 陈宇 Lg_chenyu@ 今天你AC 了吗？ 第8讲 二分和构造矩阵 快速幂运算 int?quickpow(int?m,int?n,int?k) {????int?b?=?1;???? while?(n??0)??? ?{??????????if?(n??1)? ????????????b?=?(b*m)%k;?? ????????n?=?n??1?;??? ???????m?=?(m*m)%k;??? ?}????return?b; }? 矩阵的快速幂运算 #include?cstdio const?int?MAX?=?3; typedef??struct{? ???????int??m[MAX][MAX]; }??Matrix; Matrix P={5,-7,4, 1,0,0, 0,1,0,}; Matrix P={1,0,0, 0,1,0, 0,0,1,}; Matrix?matrixmul(Matrix?a,Matrix?b) //矩阵乘法{???????int?i,j,k;???????Matrix?c;?? ?????for?(i?=?0?;?i??MAX;?i++)? ??????????for?(j?=?0;?j??MAX;j++)?? ???????????{?????????????????c.m[i][j]?=?0;? ??????????for?(k?=?0;?k??MAX;?k++)? ?c.m[i][j]?+=?(a.m[i][k]?*?b.m[k][j])%9997;????? ???????????c.m[i][j]?%=?9997;???????????? ? }?????? ?return?c; } 矩阵连乘的函数 Matrix?quickpow(long?long?n) {???????Matrix?m?=?P,?b?=?I;??????? while?(n?=?1)????? ??{?????????????if?(n??1)??????? ?????????b?=?matrixmul(b,m);?? ???????????n?=?n??1;? ????????????m?=?matrixmul(m,m);?????? ?}???? ???return?b; } fibonacci与构造矩阵 Fibonacci的基本递推公式： 求解递推方程就可以解出如下的通项公式： 封闭形式的通项公式： hdu 1021 hdu_1021： Problem Description There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2). Input Input consists of a sequence of lines, each containing an integer n. (n 1,000,000). ?Output Print the word yes if 3 divide evenly into F(n).Print the word no if not. 解题报告： 观察法 找出循环节=8 然后%8=2或 %8=6 就YES 本题也可以用矩阵乘法。 本题用循环节的做法 //自己本地打出f(1)-f(50)对3取余的值，然后用眼睛观察，找出循环节。 #include iostream using namespace std; int main() { int n; while(cinn) { int k=n%8; if (k==2||k==6) coutyesendl; else coutnoendl; } //cout Hello world! endl; return 0; } 用矩阵乘法（直接用模版即可） 最后的公式： 详细代码： #include iostream #include stdio.h #include cstring #define Mod 3 using namespace std; const int MAX = 2; typedef struct{ int m[MAX][MAX]; } Matrix; Matrix P={0,1,