M_sea

洛谷2233 [HNOI2002]公交车路线
Luogu算法和P3758类似,也是对邻接矩阵跑矩阵快速幂。但是这个邻接矩阵要这样建:$\begin{vmatri...
扫描右侧二维码阅读全文
03
2018/08

洛谷2233 [HNOI2002]公交车路线

Luogu

算法

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

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

$\begin{vmatrix}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\end{vmatrix}$

(很好理解)

然后,就没有然后了。

代码

#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;
}
最后修改:2019 年 05 月 26 日 02 : 39 PM

发表评论