M_sea

洛谷2233 [HNOI2002]公交车路线
题目描述在长沙城新建的环城公路上一共有8个公交站,分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个...
扫描右侧二维码阅读全文
03
2018/08

洛谷2233 [HNOI2002]公交车路线

题目描述

在长沙城新建的环城公路上一共有8个公交站,分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行,因此你从某一个公交站到另外一个公交站往往要换几次车,例如从公交站A到公交站D,你就至少需要换3次车。

img

Tiger的方向感极其糟糕,我们知道从公交站A到公交E只需要换4次车就可以到达,可是tiger却总共换了n次车,注意tiger一旦到达公交站E,他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。

传送门

算法

P3758类似,也是对邻接矩阵跑矩阵快速幂。

但是这个邻接矩阵要这样建:

0 1 0 0 0 0 0 1
1 0 1 0 0 0 0 0
0 1 0 1 0 0 0 0
0 0 1 0 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 1 0
0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 0

(都懂得)

然后,就没有然后了。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

const int MOD=1e9+7; 

struct Matrix {
    int x,y;
    int m[10][10];
};

Matrix Mul(Matrix a,Matrix b) {
    Matrix c; c.x=a.x,c.y=b.y;
    for (re int i=1;i<=a.x;i++)
        for (re int j=1;j<=b.y;j++) {
            c.m[i][j]=0;
            for (re int k=1;k<=a.y;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
        }
    return c;
}

Matrix FastPow(Matrix a,int k) {
    Matrix rt;
    rt.x=rt.y=a.x;
    for (re int i=1;i<=a.x;i++) //构造单位矩阵 
        for (re int j=1;j<=a.y;j++)
            rt.m[i][j]=(i==j);
    while (k) {
        if (k&1) rt=Mul(rt,a);
        a=Mul(a,a);
        k>>=1;
    }
    return rt;
}

mainint main() {
    int T; scanf("%lld",&T);
    while (T--) {
        int S; scanf("%lld",&S);
        if (S<=3) { printf("1\n"); continue; }
        Matrix A,B;
    
        A.x=1,A.y=3,B.x=3,B.y=3;
        A.m[1][1]=A.m[1][2]=A.m[1][3]=1;
        B.m[1][1]=B.m[1][3]=B.m[2][1]=B.m[3][2]=1;
        B.m[1][2]=B.m[2][2]=B.m[2][3]=B.m[3][1]=B.m[3][3]=0;
    
        A=Mul(A,FastPow(B,S-3));
        printf("%lld\n",A.m[1][1]);
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 57 PM

发表评论