思路

有四种方法，L，R，L->R，只走上面的小三角形

然后组合方案数\(2f^2+8f+10\)

然后求f，递推一下就好啦（其实是太麻烦了）

时间和空间复杂度都是\(O(n)\)

代码

#include 
    
     #include 
     
      #include 
      
       #define int long longusing namespace std;const int MOD = 1000000009;int n,f[1000100],g[1000100],times=1;int t(int x){    if(x%2)        return x/2;    return 0;}signed main(){    scanf("%lld",&n);    f[0]=0;    f[1]=2;    g[1]=4;    for(int i=2;i<=n;i++){        g[i]=(1LL*g[i-1]*2+4)%MOD;        // printf("g[%d]=%d\n",i,g[i]);    }    for(int i=2;i<=n-2;i++){        f[i]=1LL*(2*times%MOD+f[i-1]+2LL*g[t(i)]*times%MOD)%MOD;        if(i%2)            times=1LL*times*(g[t(i)]+1)%MOD;        // printf("f[%d]=%d\n",i,f[i]);    }    printf("%lld\n",(1LL*2*f[n-2]*f[n-2]%MOD+1LL*8*f[n-2]%MOD+10)%MOD);    return 0;}