这道题目第二次看的时候才彻底理解了是什么意思
把题目转化为数学模型分析后就是 有一个初始序列， 有一个进化率矩阵
求的是初始序列 与进化率矩阵进行 m 次运算后， 初始序列最后一位的答案
那么显然，可以对进化率矩阵进行快速幂计算
Example
Let's assume that P(0, 1) = P(1, 2) = 1, and at the beginning of a sub-process, the populations of 0, 1, 2 are 40, 20 and 10 respectively, then at the end of the sub-process, the populations are 0, 40 and 30 respectively.
这个栗子看懂了这题就会懂了。
Source Code:
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int N = ;
const int M = * ;
const ll P = 10000000097ll ; int n, m; struct Mat{
double mat[N][N];
}; Mat operator * (Mat a, Mat b){
Mat c;
memset(c.mat, , sizeof(c.mat));
for(int k = ; k < n; ++k){
for(int i = ; i < n; ++i){
if(a.mat[i][k] <= ) continue; //
for(int j = ; j < n; ++j){
if(b.mat[k][j] <= ) continue; //
c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
}
}
}
return c;
} Mat operator ^ (Mat a, int k){
Mat c;
for(int i = ; i < n; ++i){
for(int j = ; j < n; ++j){
c.mat[i][j] = (i == j); //init
}
}
for(; k; k >>= ){
if(k & ) c = c * a; //key
a = a * a;
}
return c;
} int main(){
int i, j, t, k, u, v, numCase = ;
while(EOF != scanf("%d%d",&n,&m)){
if( == n && == m) break;
double val;
Mat a, b;
memset(a.mat, , sizeof(a.mat));
memset(b.mat, , sizeof(b.mat));
for(i = ; i < n; ++i) b.mat[i][i] = ;
for(i = ; i < n; ++i) scanf("%lf", &a.mat[i][i]);
scanf("%d",&t);
while(t--){
scanf("%d%d%lf",&u,&v,&val);
b.mat[u][u] -= val; //
b.mat[u][v] = val; //
}
b = b ^ m;
double cur = ;
for(i = ; i < n; ++i){
cur += b.mat[i][n - ] * a.mat[i][i];
}
/*
for(i = 0; i < n; ++i){
for(j = 0; j < n; ++j){
cout << c.mat[i][j] << ' ';
}
cout << endl;
}
*/
printf("%.0lf\n",cur);
}
return ;
} /*
3 1
40 20 10
2
0 1 1.0
1 2 1.0
*/