模板：
#define maxn 1005
struct Matrix
{
int m[maxn][maxn];
}a,b,ans,res;
void init()
{
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(i==j)
a.m[i][j] = 1;
else
a.m[i][j] = 0;
}
}
}
Matrix mul(Matrix a,Matrix b)
{
Matrix c;
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
c.m[0][0] = 0;
for(int k = 1; k <= n; k ++)
c.m[i][j] += a.m[i][k]*b.m[k][j];
}
}
return c;
}
Matrix q_pow(Matrix a,int b)
{
res = a;
while(b)
{
if(b&1)
res = mul(res,a);
a = mul(a,a);
b >>= 1;
}
return res;
}In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is
.
Given an integer n, your goal is to compute the last 4 digits of Fn.
Input
The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.
Output
For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).
Sample Input
0
9
999999999
1000000000
-1 Sample Output
0 题意：求斐波那契数列的第n项
解析：利用矩阵快速幂，因为题意给出了
即求这个矩阵的n次幂，然后再输出矩阵的第一列第二个就行啦~
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<string>
#include<set>
#include<sstream>
#include<queue>
#include<cstdio>
#include<stack>
#include<cmath>
using namespace std;
const int MOD = 10000;
struct Matrix{
int a[12][12];
};
Matrix Init(){//初始化初始矩阵
Matrix a;
a.a[0][0] = 1;
a.a[0][1] = 1;
a.a[1][0] = 1;
a.a[1][1] = 0;
return a;
}
Matrix Mul(Matrix a, Matrix b, int n){//矩阵乘法
Matrix c;
for( int i=0; i<n;i++) {
for( int j=0; j<n;j++) {
c.a[i][j]=0;
for( int k=0; k<n;k++) {
c.a[i][j] += a.a[i][k]*b.a[k][j];
}
c.a[i][j] %= MOD;
}
}
return c;
}
Matrix Pow(Matrix a, int k,int n){
Matrix r = Init(),ba = a;
while(k){
if(k%2 == 1)
r = Mul(r,ba,n);
ba = Mul(ba,ba,n);
k/=2;
}
return r;
}
int main(){
int k;
while(scanf("%d",&k) != EOF && k!=-1){
if(k == 0){
printf("0\n");
continue;
}
Matrix a = Init();
Matrix res = Pow(a,k-1,2);
printf("%d\n",res.a[0][1]%MOD);
}
return 0;
}In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a 0,1 = 233,a 0,2 = 2333,a 0,3 = 23333...) Besides, in 233 matrix, we got a i,j = a i-1,j +a i,j-1( i,j ≠ 0). Now you have known a 1,0,a 2,0,...,a n,0, could you tell me a n,m in the 233 matrix?
Input
There are multiple test cases. Please process till EOF.
For each case, the first line contains two postive integers n,m(n ≤ 10,m ≤ 10 9). The second line contains n integers, a 1,0,a 2,0,...,a n,0(0 ≤ a i,0 < 2 31).
Output
For each case, output a n,m mod 10000007.
Sample Input
1 1
1
2 2
0 0
3 7
23 47 16 Sample Output
234
2799
72937
题意：给出一个矩阵的第一行第一列，求出第n行第m列，矩阵中元素有递推式a[i][j] = a[i-1][j]+a[i][j-1]。其中第一行为0,233,2333,23333...，第一列为0,x1,x2,x3...，xi在输入中给出。n<=10，m<=10^9
解析：
根据n = 3,m = 3可以构造一个矩阵
233 10 0 0 0 1 23
x1+233 10 1 0 0 1 x1
x1+x2+233 = 10 1 1 0 1 * x2
x1+x2+x3+233 10 1 1 1 1 x3
3 0 0 0 0 0 3
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct matrix
{
__int64 mat[15][15];
matrix()
{
memset(mat, 0, sizeof(mat));
}
};
int n;
const int mod = 10000007;
matrix mul(matrix B, matrix A) //左乘列矩阵
{
int i, j, k;
matrix C;
for (i = 1; i <= n + 2; i++)
for (j = 1; j <= n + 2; j++)
for (k = 1; k <= n + 2; k++)
C.mat[i][j] = (C.mat[i][j] + B.mat[i][k] * A.mat[k][j]) % mod;
return C;
}
matrix powmul(matrix A, int m)
{
matrix ans;
for (int i = 1; i <= n + 2; i++)
ans.mat[i][i] = 1;
while (m > 0)
{
if (m & 1)
ans = mul(ans, A);
A = mul(A, A);
m >>= 1;
}
return ans;
}
int main()
{
int m;
while (scanf("%d%d", &n, &m) != EOF)
{
matrix A, B;
A.mat[1][1] = 23;
for (int i = 1; i <= n; i++)
scanf("%d", &A.mat[i + 1][1]);
A.mat[n + 2][1] = 3;
for (int i = 1; i <= n + 1; i++)
B.mat[i][1] = 10;
for (int i = 1; i <= n + 2; i++)
B.mat[i][n + 2] = 1;
for (int i = 1; i < n + 2; i++)
for (int j = 2; j <= i; j++)
B.mat[i][j] = 1;
B = powmul(B, m);
A = mul(B, A);
cout << A.mat[n + 1][1] << endl;
}
return 0;
}
Shirly is a very clever girl. Now she has two containers (A and B), each with some water. Every minute, she pours half of the water in A into B, and simultaneous pours half of the water in B into A. As the pouring continues, she finds it is very easy to calculate the amount of water in A and B at any time. It is really an easy job :).
But now Shirly wants to know how to calculate the amount of water in each container if there are more than two containers. Then the problem becomes challenging.
Now Shirly has N (2 <= N <= 20) containers (numbered from 1 to N). Every minute, each container is supposed to pour water into another K containers (K may vary for different containers). Then the water will be evenly divided into K portions and accordingly poured into anther K containers. Now the question is: how much water exists in each container at some specified time?
For example, container 1 is specified to pour its water into container 1, 2, 3. Then in every minute, container 1 will pour its 1/3 of its water into container 1, 2, 3 separately (actually, 1/3 is poured back to itself, this is allowed by the rule of the game).
Input
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. And it will be followed by T consecutive test cases.
Each test case starts with a line containing an integer N, the number of containers. The second line contains N floating numbers, denoting the initial water in each container. The following N lines describe the relations that one container(from 1 to N) will pour water into the others. Each line starts with an integer K (0 <= K <= N) followed by K integers. Each integer ([1, N]) represents a container that should pour water into by the current container. The last line is an integer M (1<= M <= 1,000,000,000) denoting the pouring will continue for M minutes.
Output
For each test case, output contains N floating numbers to two decimal places, the amount of water remaining in each container after the pouring in one line separated by one space. There is no space at the end of the line.
Sample Input
1
2
100.00 100.00
1 2
2 1 2
2
Sample Output
75.00 125.00
Note: the capacity of the container is not limited and all the pouring at every minute is processed at the same time.
题意： 给出 T 组样例，再给出 N 个水杯，后给出 N 个水杯的容量，后给出 N 行，首先第一行是 K，代表要讲这个杯里面的水要分给一下 K 个水杯，后给出 K 个水杯的编号。输出 M 时间后各个水杯剩下的水容量。输出两位小数。
解析： 矩阵快速幂。构成一个 N X N 的矩阵，对这个矩阵就 M 次方最后乘以 N X 1 的矩阵，输出这个 N X 1 的矩阵即为答案。
#include<iostream>
#include<cstdio>
using namespace std;
#define maxn 100
struct Matrix{
double m[maxn][maxn];
}p,ans,a,b;
int n;
void init()
{
fill(p.m[0],p.m[maxn],0);
for(int i = 0; i < maxn; i ++)
{
p.m[i][i] = 1;
}
}
Matrix mul(Matrix a,Matrix b)
{
Matrix c;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
c.m[i][j] = 0;
for(int k = 0; k < n; k ++)
c.m[i][j] += a.m[i][k] * b.m[k][j];
}
}
return c;
}
Matrix q_pow(Matrix a,long long int b)
{
Matrix ans = p;
while(b)
{
if(b&1)
ans = mul(ans,a);
a = mul(a,a);
b>>=1;
}
return ans;
}
int main()
{
int t;
scanf("%d",&t);
init();
while(t--)
{
scanf("%d",&n);
fill(a.m[0],a.m[n],0);
for(int i = 0; i < n; i ++)
scanf("%lf",&a.m[0][i]);
fill(b.m[0],b.m[n],0);
for(int i = 0; i < n; i ++)
{
int k;
scanf("%d",&k);
if(!k)
b.m[i][i] = 1;
for(int j = 0; j < k; j ++)
{
int x;
scanf("%d",&x);
b.m[i][x-1] = 1.0/k;
}
}
long long int m;
scanf("%lld",&m);
b = q_pow(b,m);
ans = mul(a,b);
printf("%.2f",ans.m[0][0]);
for(int i = 1; i < n; i ++)
printf(" %.2f",ans.m[0][i]);
printf("\n");
}
return 0;
}