矩阵优化dp

链接：https://www.luogu.org/problemnew/show/P1939

题解：

矩阵优化dp模板题

搞清楚矩阵是怎么乘的构造一下矩阵就很简单了

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mo 1000000007
ll t,x;
struct re{
    ll jz[5][5];
}a,c;
re XX(re x,re y)
{
    re tmp; memset(tmp.jz,0,sizeof(tmp.jz));
    for (ll i=1;i<=3;i++)
      for (ll j=1;j<=3;j++)
        for (ll k=1;k<=3;k++)
          tmp.jz[i][k]=(tmp.jz[i][k]+x.jz[i][j]*y.jz[j][k])%mo;
    return(tmp);
}
re fastpow(ll x)
{
    if (x==1) return(a);
    re b=fastpow(x/2);
    b=XX(b,b);
    if (x%2==1) b=XX(b,a);
    return(b);
}
int main()
{
    freopen("noip.in","r",stdin);
    freopen("noip.out","w",stdout);
    cin>>t;
    while (t--)
    {
      memset(a.jz,0,sizeof(a.jz));
      a.jz[1][3]=1; a.jz[2][1]=1; 
      a.jz[3][2]=1; a.jz[3][3]=1;
      cin>>x;
      if (x<=3) cout<<1<<endl;
      else
      {
         c=fastpow(x-3);
           cout<<(c.jz[1][3]+c.jz[2][3]+c.jz[3][3])%mo<<endl;
      }
    
    }
    return 0;
}