2017 ACM/ICPC Asia Regional Shenyang Online E number number number 题解

分析：

当n=1时ans=4=f(5)-1;

n=2,ans=12=f(7)-1;

n=3,ans=33=f(9)-1;

于是大胆猜想ans=f(2*k+3)-1。

之后用矩阵快速幂求解f(n)即可，O(logn)。

AC code:

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef vector<ll> vec;

 typedef vector<vec> mat;

 const ll M=;

 mat mul(mat& A,mat& B)

 {

     mat C(A.size(),vec(B[].size()));

     for(int i=;i<A.size();i++)

         for(int k=;k<B.size();k++)

             for(int j=;j<B[].size();j++)

                 C[i][j]=(C[i][j]+A[i][k]*B[k][j]) % M;

     return C;

 }

 mat pow(mat A,ll n)

 {

     mat B(A.size(),vec(A.size()));

     for(int i=;i<A.size();i++)    B[i][i]=;

     while(n)

     {

         if(n&)    B=mul(B,A);

         A=mul(A,A);

         n>>=;

     }

     return B;

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     ll k;

     while(~scanf("%lld",&k))

     {

         mat A(,vec());

         A[][]=;A[][]=;

         A[][]=;A[][]=;

         A=pow(A,*k+);

         printf("%lld\n",A[][]-);

     }

     return ;

 }