首页 > 代码库 > ACdream1093

ACdream1093

2024-07-13 03:53:36   226人阅读

给你三种正多面体，正四面体，正六面体，正八面体。求从某一种正多面体中的某一点走到另一个点，且步数不超过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=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\n",(int)answer);    }    return 0;}


联系
我们