题目大意：给你三种正多边形，给你起点s，终点e以及最多行走的步数k，问有多少种路径方案（路径中只要有一个顶点不同即视为不同）。

题目分析：

可以通过矩阵快速幂求解。

为每个正多边形（最多三个）构建一个邻接矩阵A，然后第K步的方案数即为A^k。

结果即为A^1 + A^2 + A^3 + ...... + A^k.

对于这种形式的矩阵运算，我们可以把它拆分成：

k为奇：ans = （A^1 + A^2 + ... + A^(k/2)) + (A^1 + A^2 + ... + A^(k/2)) * A^(k.2) + A^k；

k为偶：ans = （A^1 + A^2 + ... + A^(k/2)) + (A^1 + A^2 + ... + A^(k/2)) * A^(k.2)；

合并一下就是：

ans = （A^1 + A^2 + ... + A^(k/2)) * (A(k/2) + 1);

if(k & 1) ans = ans + A^k;

结果即为mat[s - 1][e - 1]（保存的时候下标均以减一）。

PS：本蒟蒻的代码效率貌似一直不高的样子QUQ。。。路过的众神们见谅QUQ。。。

代码如下：

#include 
      
       #include 
       
        #define REP(i, n) for(int i = 0; i < n; ++i)typedef long long ll;const int mod = 1000000007;const int O = 8;int N, K;typedef struct M{    ll mat[O][O];    M operator * (const M &t) const{
    //重载矩阵乘法        M tmp;        memset(tmp.mat, 0, sizeof(tmp.mat));        REP(i, N) REP(j, N) REP(k, N) tmp.mat[i][j] = (tmp.mat[i][j] + mat[i][k] * t.mat[k][j]) % mod;        return tmp;    }        //不使用函数的原因是为了让快速幂看起来更加自然        M operator + (const M &t) const{
    //重载矩阵加法        M tmp;        REP(i, N) REP(j, N) tmp.mat[i][j] = (mat[i][j] + t.mat[i][j]) % mod;        return tmp;    }}M;M A[3] = {    {
     {
     //正四边形    {
    0, 1, 1, 1},    {
     1, 0, 1, 1},    {
     1, 1, 0, 1},    {
     1, 1, 1, 0},    }},    {
     {
     //正六边形    {
    0, 1, 0, 1, 1, 0, 0, 0},    {
     1, 0, 1, 0, 0, 1, 0, 0},    {
     0, 1, 0, 1, 0 ,0, 1, 0},    {
     1, 0, 1, 0, 0, 0, 0, 1},    {
     1, 0, 0, 0, 0, 1, 0, 1},    {
     0, 1, 0, 0, 1, 0, 1, 0},    {
     0, 0, 1, 0, 0 ,1, 0, 1},    {
     0, 0, 0, 1, 1, 0, 1, 0},    }},    {
     {
     //正八边形    {
    0, 1, 1, 1, 1, 0},    {
     1, 0, 1, 0, 1, 1},    {
     1, 1, 0, 1, 0, 1},    {
     1, 0, 1, 0, 1, 1},    {
     1, 1, 0, 1, 0, 1},    {
     0, 1, 1, 1, 1, 0},    }},}, E;M pow(ll k){
     //矩阵快速幂求A^k.    M res = E, tmp = A[K];    for(; k; k >>= 1){        if(k & 1) res = res * tmp;        tmp = tmp * tmp;    }    return res;}M _pow(ll k){
     //递归快速幂求A^1 + A^2 + A^3 + ...... + A^k.    if(k == 1) return A[K];    M res = _pow(k >> 1) * (E + pow(k >> 1));    if(k & 1) res = res + pow(k);    return res;}void work(){    int t, n, s, e;    ll k;    REP(i, O) REP(j, O) E.mat[i][j] = (i == j);//初始化单位矩阵    scanf("%d", &t);    while(t--){        scanf("%d%lld%d%d", &n, &k, &s, &e);        N = (n == 4 ? 4 : (n == 6 ? 8 : 6));//选择矩阵需要的范围        K = (n == 4 ? 0 : (n == 6 ? 1 : 2));//选择正多边形的类型        printf("%lld\n", _pow(k).mat[s - 1][e - 1]);    }}int main(){    work();    return 0;}
       
      

在此附上ACdream区域赛指导赛之专题赛系列(1)の数学专场解题报告，本题即E题。http://acdream.info/topic/1451