给你三种正多面体，正四面体，正六面体，正八面体。求从某一种正多面体中的某一点走到另一个点，且步数不超过k(1018)的方案数。
首先说明一下我交题的时候遇到的问题，起点和终点为同一点的时候，算不算走了零步到达了？题目没有算，如果考虑了交上去会wa。
题目解法是矩阵。
一开始通过观察这三种多面体，得出初始矩阵。 这里要细心。
显然我们可以通过矩阵乘法迅速地知道从一点到另一点走k步的方案数。假设矩阵是a[][]，那么x->y的方案就是a[x][y]。
要求不超过k步的方案，就相当于前k个矩阵求和了（前k次方和）。因为矩阵有很多性质跟数是一样的，我们可以用类似的方法求解。
我也不知道自己用的是什么方法，反正这样写可以过。不过好像时间上不是最优的。
召唤代码君：
/*
* this code is made by 092000
* Problem: 1093
* Verdict: Accepted
* Submission Date: 2014-07-20 10:06:15
* Time: 592MS
* Memory: 1676KB
*/
#include <iostream>
#include <cstdio>
#include <cstring>
typedef long long ll;
using namespace std; const int mod=;
ll k;
int n,I,J,T; int a4[][]={
{,,,},
{,,,},
{,,,},
{,,,},
}; int a6[][]={
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
{,,,,,},
}; int a8[][]={
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
{,,,,,,,},
}; struct mat{
ll a[][];
void init0()
{
memset(a,,sizeof a);
}
void init1()
{
init0();
for (int i=; i<n; i++) a[i][i]=;
}
void init(int x)
{
init0();
if (x==)
{
for (int i=; i<; i++)
for (int j=; j<; j++) a[i][j]=a4[i][j];
}
else if (x==)
{
for (int i=; i<; i++)
for (int j=; j<; j++) a[i][j]=a6[i][j];
}
else
{
for (int i=; i<; i++)
for (int j=; j<; j++) a[i][j]=a8[i][j];
}
}
}; mat add(mat e1,mat e2)
{
mat e0;
for (int i=; i<n; i++)
for (int j=; j<n; j++)
e0.a[i][j]=(e1.a[i][j]+e2.a[i][j])%mod;
return e0;
} mat mul(mat e1,mat e2)
{
mat e0;
e0.init0();
for (int i=; i<n; i++)
for (int j=; j<n; j++)
for (int k=; k<n; k++) e0.a[i][j]=(e0.a[i][j]+e1.a[i][k]*e2.a[k][j])%mod;
return e0;
} mat power(mat e,ll y)
{
mat e0;
e0.init1();
while (y)
{
if (y&) e0=mul(e0,e);
e=mul(e,e),y>>=;
}
return e0;
} int main()
{
mat ans,tmp,squ,E;
ll answer;
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
scanf("%lld",&k);
scanf("%d",&I);
scanf("%d",&J);
//scanf("%d%lld%d%d",&n,&k,&I,&J);
if (n==) n=;
else if (n==) n=;
ans.init0();
tmp.init1();
squ.init1();
E.init(n);
while (k)
{
if (k&) ans=add(ans,mul(tmp,power(E,k)));
k>>=;
tmp=mul(tmp,add(power(E,k),squ));
}
answer=ans.a[I-][J-];
//if (I==J) answer++;
answer%=mod;
printf("%d\n",(int)answer);
}
return ;
}