题目背景
在长沙城新建的环城公路上一共有8个公交站，分别为A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行，因此你从某一个公交站到另外一个公交站往往要换几次车，例如从公交站A到公交站D，你就至少需要换3次车。
Tiger的方向感极其糟糕，我们知道从公交站A到公交E只需要换4次车就可以到达，可是tiger却总共换了n次车，注意tiger一旦到达公交站E，他不会愚蠢到再去换车。现在希望你计算一下tiger有多少种可能的乘车方案。
题目描述
输入输出格式
输入格式：
仅有一个正整数n(4<=n<=10000000)，表示tiger从公交车站A到公交车站E共换了n次车。
输出格式：
仅有一个正整数，由于方案数很大，请输出方案数除以 1000后的余数。
输入输出样例
6
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)。
题解：
看到数据范围n<=10000000。想到肯定要O(n)才能过。
O(n）算法复杂度+一个输入输出，肯定就是递推啦
可是递推公式？？
暴力算前几个答案是
4 5 6 7 8 9 10 11 12 13 14
2 0 8 0 28 0 96 0 328 0 1120
发现当n为奇数时，ans=0；
开始想递推式
设f[i]=x*f[i-1]+y; 解出答案后代入后面是不成立的
设f[i]=x*f[i-1]+y*f[i-2]+z;
28=8x+2y+z; 96=28x+8y+z; 328=96x+28y+z;
解得 x=4;y=-2;z=0;带入后面也是成立的
于是，递推式就出来了，f[i]=4*f[i-1]-2*f[i-2];
一个非常坑的地方：由于答案%1000后f[i-2]有可能大于f[i-1]
所以极端情况下，f[i-2]=999,f[i-1]=0;所以如代码所示，还要+2000后再%1000
#include<iostream> using namespace std; int f[10000010]; int main() { int n;cin>>n; if(n&1)cout<<0; else { f[4]=2;f[6]=8; for(int i=8;i<=n;i+=2)f[i]=(4*f[i-2]-2*f[i-4]+2000)%1000; cout<<f[n]; } return 0; }
代码居然才写了15行。。。这是省选题啊
那如果加强这个数据，变为有T组数据,每组数据的n变为4<=n<=10^18怎么做呢
那我们可以用矩阵快速幂优化到O(Tlog(n))
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int mod=1000; struct data{ int d[5][5]; }a,b,c; data mul(data a,data b) { memset(c.d,0,sizeof(c.d)); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) { c.d[i][j]=(c.d[i][j]+a.d[i][k]*b.d[k][j])%mod; } return c; } int main() { int T;scanf("%d",&T); while(T--) { long long n;scanf("%lld",&n); if(n&1)printf("0 "); else { b.d[0][0]=0;b.d[0][1]=1;b.d[1][0]=-2+mod;b.d[1][1]=4; a.d[0][0]=1;a.d[0][1]=0;a.d[1][0]=1;a.d[1][1]=0; n=(n-4)/2; while(n) { if(n&1)a=mul(a,b); b=mul(b,b);n>>=1; } printf("%d ",(a.d[0][0]*2+a.d[0][1]*8)%mod); } } return 0; }