题解
构造递推关系，设$f(p,n)$表示换了$n$次车到了$p$点的方案数，发现F点与D点均只能由上一个点转移而来，E点由F与D点转移而来，其余点由两侧的点转移而来。
由此得到递推方程，但是$n$太大，故使用矩阵乘法加速。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
struct Mat{
int dat[10][10],r,c;
Mat(int a,int b){
this->r=a,this->c=b,
memset(this->dat,0,sizeof(this->dat));
}
};
int Mod=1000,n,dx[]={0,0,1,1,2,2,3,3,4,4,5,6,7,7},
dy[]={1,2,0,3,0,4,1,5,2,6,3,4,5,6};
void mul(Mat &a,Mat &b,Mat &newed){
newed.r=a.r,newed.c=b.c;
int i,j,k,t;
for(i=0;i<a.r;i++)
for(j=0;j<b.c;j++){
for(t=0,k=0;k<a.c;k++)t+=(a.dat[i][k])*(b.dat[k][j]),t%=Mod;
newed.dat[i][j]=t%Mod;
}
}
Mat pow(Mat a,int p){
Mat E(a.c,a.c),F(a.c,a.c);
int i,j;
for(i=0;i<a.c;i++)
for(j=0;j<a.c;j++)
E.dat[i][j]=(i==j)?1:0;
while(p){
if(p&1)mul(E,a,F),E=F;
mul(a,a,F),a=F,p>>=1;
}
return E;
}
int main(){
n=read();
Mat q(8,8),s(8,1),e(8,1);
for(int i=0;i<14;i++)
q.dat[dx[i]][dy[i]]=1;
s.dat[0][0]=1;
q=pow(q,n),mul(q,s,e);
printf("%d\n",e.dat[7][0]);
return 0;
}