ACdream1093

给你三种正多面体，正四面体，正六面体，正八面体。求从某一种正多面体中的某一点走到另一个点，且步数不超过k(10¹⁸)的方案数。

首先说明一下我交题的时候遇到的问题，起点和终点为同一点的时候，算不算走了零步到达了？题目没有算，如果考虑了交上去会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=1000000007;
ll k;
int n,I,J,T;
 
int a4[4][4]={
        {0,1,1,1},
        {1,0,1,1},
        {1,1,0,1},
        {1,1,1,0},
    };
     
int a6[6][6]={
        {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},
};
     
int a8[8][8]={
        {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},
};
 
struct mat{
    ll a[8][8];
    void init0()
        {
            memset(a,0,sizeof a);
        }
    void init1()
        {
            init0();
            for (int i=0; i<n; i++) a[i][i]=1;
        }
    void init(int x)
    {
        init0();
        if (x==4)
        {
            for (int i=0; i<4; i++)
                for (int j=0; j<4; j++) a[i][j]=a4[i][j];
        }
        else if (x==6)
        {
            for (int i=0; i<6; i++)
                for (int j=0; j<6; j++) a[i][j]=a6[i][j];
        }
        else
        {
            for (int i=0; i<8; i++)
                for (int j=0; j<8; j++) a[i][j]=a8[i][j];
        }
    }
};
 
mat add(mat e1,mat e2)
{
    mat e0;
    for (int i=0; i<n; i++)
        for (int j=0; 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=0; i<n; i++)
        for (int j=0; j<n; j++)
            for (int k=0; 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&1) e0=mul(e0,e);
        e=mul(e,e),y>>=1;
    }
    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==8) n=6;
            else if (n==6) n=8;
        ans.init0();
        tmp.init1();
        squ.init1();
        E.init(n);
        while (k)
        {
            if (k&1) ans=add(ans,mul(tmp,power(E,k)));
            k>>=1;
            tmp=mul(tmp,add(power(E,k),squ));
        }
        answer=ans.a[I-1][J-1];
        //if (I==J) answer++;
        answer%=mod;
        printf("%d
",(int)answer);
    }
    return 0;
}