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=;

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 ;

}