矩阵学习笔记

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

题目链接 题意：求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。 思路：先用扩展欧几里得算法（excrt）解一般同余方程求出一个特解R，然后通解R’ = R + k * LCM(a1..am)

题目链接 题意：给出k个方程，形式为 x==r1，求最小的正数x，无解输出-1. 思路：首先很容易让人联想到crt. 然而crt的使用条件是，所有的m(也就是这道题中的a)两两互质，这道题并不满足，因此不能使用crt.

题目链接： **题意：**人自出生起就有体力，情感和智力三个生理周期，分别为23，28和33天。一个周期内有一天为峰值，在这一 天，人在对应的方面（体力，情感或智力）表现最好。通常这三个周期的峰值不会是同一天。现在给出三个日