矩阵优化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[][];

}a,c;

re XX(re x,re y)

{

    re tmp; memset(tmp.jz,,sizeof(tmp.jz));

    for (ll i=;i<=;i++)

      for (ll j=;j<=;j++)

        for (ll k=;k<=;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==) return(a);

    re b=fastpow(x/);

    b=XX(b,b);

    if (x%==) 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,,sizeof(a.jz));

      a.jz[][]=; a.jz[][]=;

      a.jz[][]=; a.jz[][]=;

      cin>>x;

      if (x<=) cout<<<<endl;

      else

      {

         c=fastpow(x-);

           cout<<(c.jz[][]+c.jz[][]+c.jz[][])%mo<<endl;

      }

    }

    return ;

}