给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
时间：2016-09-02 16:57:42
时间：2016-09-02 16:57:42
把给定的图转为邻接矩阵， 即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经 过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分 求出A^k即可。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10
using namespace std;
const int mod = 7777777;
typedef long long LL;
struct matrix{
LL a[10][10];
}origin;
int n,m;
matrix multiply(matrix x,matrix y)
{
matrix temp;
memset(temp.a,0,sizeof(temp.a));
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
{
for (int k=0;k<n;k++)
{
temp.a[i][j]+=x.a[i][k]*y.a[k][j];
temp.a[i][j]=(temp.a[i][j])%mod;
}
}
}
return temp;
}
matrix matmod(matrix A,int k)
{
matrix res;
memset(res.a,0,sizeof res.a);
for (int i=0;i<n;i++) res.a[i][i]=1;
while(k)
{
if (k&1) res=multiply(res,A);
k>>=1;
A=multiply(A,A);
}
return res;
}
void print(matrix x)
{
for (int i=0;i<n;i++)
{
for (int j=0;j<n;j++)
cout<<" "<<x.a[i][j];puts("");
}
printf("---------------\n");
}
int main()
{
int k;
while (cin>>n>>k)
{
memset(origin.a,0,sizeof origin.a);
origin.a[0][0]=1;
for (int i=1;i<=n;i++)
{
origin.a[i][0]=1;
for (int j=0;j<i;j++)
origin.a[i][0]+=origin.a[j][0];
}
// print(origin);
matrix res;
memset(res.a,0,sizeof res.a);
for (int i=0;i<n-1;i++)
res.a[i][i+1]=1;
for (int i=0;i<n;i++) res.a[n-1][i]=1;
//print(res);
res=matmod(res,k-1);
LL fans=0;
for (int i=0;i<n;i++)
{
fans+=res.a[0][i]*origin.a[i][0];
fans%=mod;
}
cout<<fans<<endl;
}
return 0;
}
