网站设计接单友情链接的四个技巧

[HNOI2002] 公交车路线

题目描述

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

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

输入格式

仅有一个正整数 $n$，表示 tiger 从公交车站 A 到公交车站 E 共换了 $n$ 次车。

输出格式

输出一个正整数表示方案数，由于方案数很大，请输出方案数除以 $1000$ 后的余数。

样例 #1

样例输入 #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)。

数据范围

$4\le n\le 10^7$。

思路

• 对于这种求最优方案数，我们很容易发现，对于任意一点，我们设 $f_{i,j}$ 为所有走了 $i$ 次，到达 $j$ 点。
• 状态转移：$f_{i,j}=f_{i-1,j-1}+f_{i-1,j+1}$。
• 如果我们把次数这一维度暂时不看，你不发现这很像是斐波那契数列吗，而且本道题的 $n$ 特别大，因此我们得加速，就可以想到矩阵加速。
• 因此我们可以这样做，把第一维度的次数放到指数上去。也就是最终我们就是求：
  $$(f_A,f_B,f_C,...f_H)=(f_A,f_B,f_C,...f_H)A^n$$，其中 $A$ 矩阵为我们构造的矩阵，$n$ 为次数，初始的时候我们是从 $f_A$ 开始，因此我们最开始设 $f_A=1$，最后的答案是 $f_D+f_F$。
• 那个 $A$ 矩阵想必大家也懂得怎么写，就是你得记住这个公式： $f_j=f_{j-1}+f_{j+1}$。
• 

AC 代码

#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;const int N = 8 ,mod=1000;int f1[N];
int A[N][N]={{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, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 0, 0, 0, 0, 1, 0},{0, 0, 0, 0, 0, 1, 0, 1},{1, 0, 0, 0, 0, 0, 1, 0},
};int n;void mul(int c[],int a[],int b[][N]){int temp[N]={0};for(int i=0;i<N;i++){for(int j=0;j<N;j++){temp[i]=(temp[i]+a[j]*b[j][i])%mod;}}memcpy(c,temp,sizeof temp);
}void mul(int c[][N],int a[][N],int b[][N]){int temp[N][N]={0};for(int i=0;i<N;i++){for(int j=0;j<N;j++){for(int k=0;k<N;k++){temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%mod;}}}memcpy(c,temp,sizeof temp);
}int main(){cin>>n;n--;f1[0]=1;while(n){if(n&1)mul(f1,f1,A);mul(A,A,A);n>>=1;}cout<<(f1[3]+f1[5])%mod;return 0;}