CF15E Triangles

思路

有四种方法，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;

}

巴特西

CF15E Triangles

思路

代码

最新文章

热门文章