wordpress怎么可视化构建页面,怀化网站优化,从零学习做网站,江苏网站建设案例[HNOI2002] 公交车路线
题目描述
在长沙城新建的环城公路上一共有 8 8 8 个公交站#xff0c;分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行#xff0c;因此你从某一个公交站到另外一个公交站往往要换几次车#xff0c;例如从公交站 A 到公交…[HNOI2002] 公交车路线
题目描述
在长沙城新建的环城公路上一共有 8 8 8 个公交站分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行因此你从某一个公交站到另外一个公交站往往要换几次车例如从公交站 A 到公交站 D你就至少需要换 3 3 3 次车。 Tiger 的方向感极其糟糕我们知道从公交站 A 到公交 E 只需要换 4 4 4 次车就可以到达可是 tiger 却总共换了 n n n 次车注意 tiger 一旦到达公交站 E他不会愚蠢到再去换车。现在希望你计算一下 tiger 有多少种可能的乘车方案。
输入格式
仅有一个正整数 n n n表示 tiger 从公交车站 A 到公交车站 E 共换了 n n n 次车。
输出格式
输出一个正整数表示方案数由于方案数很大请输出方案数除以 1000 1000 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 ≤ n ≤ 1 0 7 4\le n\le10^7 4≤n≤107。
思路
对于这种求最优方案数我们很容易发现对于任意一点我们设 f i , j f_{i,j} fi,j 为所有走了 i i i 次到达 j j j 点。状态转移 f i , j f i − 1 , j − 1 f i − 1 , j 1 f_{i,j}f_{i-1,j-1}f_{i-1,j1} fi,jfi−1,j−1fi−1,j1。如果我们把次数这一维度暂时不看你不发现这很像是斐波那契数列吗而且本道题的 n n n 特别大因此我们得加速就可以想到矩阵加速。因此我们可以这样做把第一维度的次数放到指数上去。也就是最终我们就是求 ( f A , f B , f C , . . . f H ) ( f A , f B , f C , . . . f H ) A n (f_A,f_B,f_C,...f_H)(f_A,f_B,f_C,...f_H)A^{n} (fA,fB,fC,...fH)(fA,fB,fC,...fH)An其中 A A A 矩阵为我们构造的矩阵 n n n 为次数初始的时候我们是从 f A f_A fA 开始因此我们最开始设 f A 1 f_A1 fA1最后的答案是 f D f F f_Df_F fDfF。那个 A A A 矩阵想必大家也懂得怎么写就是你得记住这个公式 f j f j − 1 f j 1 f_{j}f_{j-1}f_{j1} fjfj−1fj1。
AC 代码
#includeiostream
#includealgorithm
#includecstringusing namespace std;const int N 8 ,mod1000;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 i0;iN;i){for(int j0;jN;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 i0;iN;i){for(int j0;jN;j){for(int k0;kN;k){temp[i][j](temp[i][j]a[i][k]*b[k][j])%mod;}}}memcpy(c,temp,sizeof temp);
}int main(){cinn;n--;f1[0]1;while(n){if(n1)mul(f1,f1,A);mul(A,A,A);n1;}cout(f1[3]f1[5])%mod;return 0;}
