B20J_1297_[SCOI2009]迷路_矩阵乘法
题意：
有向图 N 个节点，从节点 0 出发，必须恰好在 T 时刻到达节点 N-1。总共有多少种不同的路径？
2 <= N <= 10 ； 1 <= T <= 1000000000 边权范围[1,9].
分析：
首先看题目数据性质，N很小，即使是完全图边数也不会超过100。因此我们可以利用矩阵乘法优化。
如何优化：1.我们发现，当边权为1时每走一步就相当于乘上一次图的邻接矩阵。可以用矩阵快速幂O(N^3*logT）快速解决；
2.如果边权不为1我们可以运用拆点的技巧，把边拆成等同边权长度个点。
代码：
值得注意的是答案应是所求点的入点，而不是所有小点求和。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define mem(x) memset(&x,0,sizeof(x))
#define LL long long
LL f[91][91],n,t,cnt,p=2009;
struct mat
{
LL v[91][91];
};
mat mul(const mat &x,const mat &y)
{
mat re;mem(re);
for(int i=1;i<=cnt;i++)
{
for(int j=1;j<=cnt;j++)
{
for(int k=1;k<=cnt;k++)
{
re.v[i][j]=(re.v[i][j]+x.v[i][k]*y.v[k][j])%p;
}
}
}
return re;
}
void pow()
{
mat I,x;mem(I);mem(x);
for(int i=1;i<=9*n;i++)I.v[i][i]=1;
for(int i=1;i<=9*n;i++)
{
for(int j=1;j<=9*n;j++)
{
x.v[i][j]=f[i][j];
}
}
while(t)
{
if(t&1)I=mul(I,x);
x=mul(x,x);
t>>=1;
}
printf("%lld",I.v[1][(n-1)*9+1]%p);
}
int main()
{
scanf("%d%d",&n,&t);
cnt=9*n;
int x;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&x);
int now=(i-1)*9+1;
if(!x)continue;
if(x==1)f[(i-1)*9+1][(j-1)*9+1]=1;
else
{
for(int k=1;k<=x;k++)
{
if(k==x)
{
f[now][(j-1)*9+1]=1;break;
}
f[now][now+1]=1;
now++;
}
}
}
}
pow();
}
/***************************************************************
Problem: 1113
User: 20170105
Language: C++
Result: Accepted
Time:616 ms
Memory:1104 kb
****************************************************************/
