【题目大意】
求
% m
【算法分析】
首先我们发现答案是指关于n的一个函数。
那么我们把小数据暴力一下，得到下表：
0 0 0
1 1 1
2 3 2
3 8 5
4 21 13
5 55 34
6 144 89
7 377 233
8 987 610
9 2584 1597
10 6765 4181
11 17711 10946
12 46368 28657
13 121393 75025
14 317811 196418
15 832040 514229
16 2178309 1346269
17 5702887 3524578
18 14930352 9227465
19 39088169 24157817
20 102334155 63245986
21 267914296 165580141
22 701408733 433494437
23 1836311903 1134903170
24 4807526976 2971215073
25 12586269025 7778742049
26 32951280099 20365011074
27 86267571272 53316291173
28 225851433717 139583862445
29 591286729879 365435296162
30 1548008755920 956722026041
其中第一个是序号，第二个是答案，第三个是ans[i]-ans[i-1]。
设第三个是p[i]，那么容易发现p[i]=3*p[i-1]-p[i-2]。
然后列出矩阵求解即可。
【其它】
居然WA了好多遍。。。真不可饶恕啊= =。
WA的原因是：n=0时没有答案输出来。。。。
【CODE】
#include
typedef __int64 lld;
lld n,mod;
lld a[1][3];
lld c[3][3],p[3][3],res[3][3];
void Pow(lld cf){
if (cf==1){
memcpy(p,c,sizeof(c));
return;
}
lld i,j,k;
Pow(cf/2);
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*p[k][j])%mod;
memcpy(p,res,sizeof(res));
if (cf%2){
memset(res,0,sizeof(res));
for (i=0;i<3;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=(res[i][j]+p[i][k]*c[k][j])%mod;
memcpy(p,res,sizeof(res));
}
}
void solve(){
a[0][0]=1; a[0][1]=1; a[0][2]=2;
c[0][0]=1; c[0][1]=0; c[0][2]=0;
c[1][0]=0; c[1][1]=0; c[1][2]=-1;
c[2][0]=1; c[2][1]=1; c[2][2]=3;
Pow(n-1);
lld i,j,k;
memset(res,0,sizeof(res));
for (i=0;i<1;i++)
for (j=0;j<3;j++)
for (k=0;k<3;k++)
res[i][j]=((res[i][j]+a[i][k]*p[k][j])%mod+mod)%mod;
cout << (res[0][0]+mod)%mod << "n";
}
int main(){
lld Tc;
cin >> Tc;
for (lld i=0;i
if (n==0) cout << "0n";
if (n==1) cout << 1%mod << "n";
if (n>=2) solve();
}
}