首页 > 代码库 > 【模板】矩阵快速幂 洛谷P2233 [HNOI2002]公交车路线
【模板】矩阵快速幂 洛谷P2233 [HNOI2002]公交车路线
P2233 [HNOI2002]公交车路线
题目背景
在长沙城新建的环城公路上一共有8个公交站，分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站A到公交站D，你就至少需要换3次车。
Tiger的方向感极其糟糕，我们知道从公交站A到公交E只需要换4次车就可以到达，可是tiger却总共换了n次车，注意tiger一旦到达公交站E，他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。
题目描述
输入输出格式
输入格式：输入文件由bus.in读入，输入文件当中仅有一个正整数n(4<=n<=10000000)，表示tiger从公交车站A到公交车站E共换了n次车。
输出格式：输出到文件bus.out。输出文件仅有一个正整数，由于方案数很大，请输出方案数除以 1000后的余数。
输入输出样例
输入样例#1：
6
输出样例#1：
8
说明
8条路线分别是：
(A→B→C→D→C→D→E)，(A→B→C→B→C→D→E)，
(A→B→A→B→C→D→E)，(A→H→A→B→C→D→E)，
(A→H→G→F→G→F→E)，(A→H→G→H→G→F→E)，
(A→H→A→H→G→F→E)，(A→B→A→H→G→F→E)。
矩阵快速幂。
把这个题看做一个图，存到邻接矩阵里。
设GK[i][j]表示从i走到j有路径长度为k的路径条数。G1就是邻接矩阵
转移：G2k[i][j] = Σ(Gk[i][k] * Gk[k][j])
不难发现Gk = G1^k
至于快速幂，把原来的快速幂直接改过来就可以了
洛谷辣鸡分类！这是第三道分类里说是线段树结果没法用线段树做的题了！
完
1 #include <bits/stdc++.h> 2 const int INF = 0x3f3f3f3f; 3 const int MOD = 1000; 4 inline void read(int &x){ 5 x = 0;char ch = getchar();char c = ch; 6 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 7 while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘,ch = getchar(); 8 if(c == ‘-‘)x = -x; 9 }10 11 long long tmp[9][9];12 long long a[9][9],b[9][9];13 14 void mul(long long a[9][9], long long b[9][9], long long c[9][9]){15 memset(tmp, 0, sizeof(tmp));16 for(int k = 1;k <= 8;k ++)17 {18 for(int i = 1;i <= 8;i ++)19 {20 for(int j = 1;j <= 8;j ++)21 { 22 tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % MOD;23 }24 }25 }26 for(int i = 1;i <= 8;i ++)27 {28 for(int j = 1;j <= 8;j ++)29 {30 c[i][j] = tmp[i][j] % MOD;31 }32 }33 }34 35 void pow(int n)36 {37 for(int i = 1;i <= 8;i ++)b[i][i] = 1;38 mul(b, a, b);39 while(n)40 {41 if(n & 1)mul(a, b, a);42 mul(b, b, b);43 n >>= 1;44 }45 }46 int nn;47 int main(){48 read(nn);49 for(int i = 1;i <= 7;i ++)a[i][i + 1] = a[i + 1][i] = 1;50 a[5][6] = a[5][4] = 0;51 a[1][8] = a[8][1] = 1;52 pow(nn - 1);53 printf("%d", a[1][5] % MOD);54 return 0;55 }
【模板】矩阵快速幂 洛谷P2233 [HNOI2002]公交车路线
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。