思路

有四种方法，L，R，L->R，只走上面的小三角形
然后组合方案数\(2f^2+8f+10\)
然后求f，递推一下就好啦（其实是太麻烦了）
时间和空间复杂度都是\(O(n)\)

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using 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;
}