题目链接：
题意：给出一个带权有向图，权值为1-9，顶点个数最多为10。从1出发恰好在T时刻到达n的路径有多少条？
思路：T较大，应使用矩阵。矩阵要求边权为1.因此，将每个点i拆为9个点，i1到i9，前一个向后一个连边1。对于原图中的边<u,v,w>，u拆完后的第w个点向v拆完后第一个点连边1。求矩阵T次幂即可。
#include <iostream>
#include <cstdio>#include <string.h>#include <algorithm>#include <cmath>#include <vector>#include <queue>#include <set>#include <stack>#include <string>#include <map>#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define FOR0(i,x) for(i=0;i<x;i++)#define FOR1(i,x) for(i=1;i<=x;i++)#define FOR(i,a,b) for(i=a;i<=b;i++)#define FORL0(i,a) for(i=a;i>=0;i--)#define FORL1(i,a) for(i=a;i>=1;i--)#define FORL(i,a,b)for(i=a;i>=b;i--)#define rush() int C; for(scanf("%d",&C);C--;)#define Rush(n) while(scanf("%d",&n)!=-1)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%lld",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%lld\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(double x) {printf("%.4lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<<x<<endl;}const int mod=100000007;const i64 inf=((i64)1)<<40;const double dinf=1000000000000000000.0;const int INF=2000000000;const int HASHSIZE=100007;const int N=1000005;int n,m;struct Matrix{ int a[95][95]; void init(int x) { clr(a,0); int i; if(x==1) { FOR1(i,n) a[i][i]=1; } } Matrix operator*(Matrix p) { Matrix ans; ans.init(0); int i,j,k; FOR1(k,n) FOR1(i,n) FOR1(j,n) { ans.a[i][j]+=a[i][k]*p.a[k][j]; ans.a[i][j]%=2009; } return ans; } Matrix pow(int m) { Matrix ans,p=*this; ans.init(1); while(m) { if(m&1) ans=ans*p; p=p*p; m>>=1; } return ans; }};Matrix a;char s[15][15];int cal(int x,int y){ return (x-1)*9+y;}int main(){ RD(n,m); int i; FOR1(i,n) RD(s[i]+1); a.init(0); int j; FOR1(i,n) { FOR1(j,8) a.a[cal(i,j)][cal(i,j+1)]=1; } FOR1(i,n) FOR1(j,n) if(s[i][j]!='0') { a.a[cal(i,s[i][j]-'0')][cal(j,1)]=1; } n*=9; a=a.pow(m); int ans=a.a[cal(1,1)][cal(n/9,1)]; PR(ans);}