JDOJ3011 铺地板III

JDOJ3011 铺地板III

https://neooj.com/oldoj/problem.php?id=3011

题目描述

有3 x N (0 <= N <= 10⁵)的网格，需要用1 x 2的瓷砖铺满。

问有多少种铺设方案。

如图，是一个3 x 12的一种铺设方案。

输入

输入一个整数N，表示是一个3 x N的网格。

输出

输出一个整数，表示铺设方案总数，答案可能会很大，结果模上2333333。

样例输入

2

样例输出

3

 

铺地板系列的巅峰！！

好好理解

不多说了上代码

#include<bits/stdc++.h>
int f[100100];   
int main()
{    
    int n;
    scanf("%d",&n);
    f[0]=1;
    f[1]=2;
    f[2]=3;
    f[3]=8;
    if(n%2!=0)
    {
        printf("0");
    }
    else
    {
        for(int i=3;i<=n;i++)
        {
            if(i%2==0)
                f[i]=(f[i-1]+f[i-2])%2333333;
            else 
                f[i]=(f[i-1]*2+f[i-2])%2333333;
        }
        printf("%d",f[n]);
    }
    return 0;
}