电子商务物流网站建设规划方案,番禺公司网站建设,wordpress 标签 图片,漫画驿站网页设计图纸尺寸大小题目描述
在长沙城新建的环城公路上一共有 8 个公交站#xff0c;分别为 A、B、C、D、E、F、G、H。公共汽车只能够在相邻的两个公交站之间运行#xff0c;因此你从某一个公交站到另外一个公交站往往要换几次车#xff0c;例如从公交站 A 到公交站 D#xff0c;你就至少需要…题目描述
在长沙城新建的环城公路上一共有 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复制
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≤10^7。 first,通过dp或超强的找规律方法得到递推式
f[i] f[i] * 4 - f[i-1] * 2;
then,设矩阵 a b c d
前五项 0 2 8 28 96
得到 2a8b8
2c8d28
8a28b28
8c28d96
解得矩阵为
0 1
-2 4
then ,求其k1项
欧克
#includebits/stdc.h
using namespace std;
//#pragma GCC optimize(2)
#define endl \n
#define lowbit(x) ((x)-(x))
const int mod1e3;
typedef long long ll;
ll ans0,n1,m1;
ll t0,s10,s20,s30,s40,max10,max20,w,min1100000000,sum0,n,m,i,j,k,v,l,r;inline int read() {bool sym0;int res0;char chgetchar();while(!isdigit(ch))sym |(ch -),chgetchar();while(isdigit(ch)) res (res3)(res1)(ch^48),chgetchar();return sym ? -res : res;
}
void print(int x) {if(!x)return;print(x/10);putchar(x%100);
}
int isPrime(int n) {float n_sqrt;if(n1) return 0;if(n2 || n3) return 1;if(n%6!1 n%6!5) return 0;n_sqrtfloor(sqrt((float)n));for(int i5; in_sqrt; i6) {if(n%(i)0 | n%(i2)0) return 0;}return 1;}
ll a[107]{0,0,2,8,28};
//矩阵快速幂
struct mm {ll m[107][108];
} as,ass;
mm operator *(const mma,const mmb ) {mm c ;memset(c.m ,0,sizeof c.m );for(ll i1; in; i) {for(ll j1; jn; j) {for(ll k1; kn; k) {c.m [i][j](c.m[i][j]a.m[i][k]*b.m[k][j])%mod;}}}return c;
}
mm qmm(mm a,ll k) {mm ans;memset(ans.m ,0,sizeof ans.m );for(ll i1; in; i)ans.m [i][i]1;while(k) {if(k1)ansans*a;aa*a;k1;}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cink;
k1;
n2;
as.m [1][1]0;
as.m [1][2]1;
as.m [2][1]-2;
as.m [2][2]4;assqmm(as,k);coutabs(ass.m [1][1]);return 0;
}//mio lover
