동물원

BOJ [동물원] 1309

DP

[-] Collapse

#include<cstdio>
#include<cstring>
using namespace std;
int cache[3][100000], n;
int search(int c, int i){
    if (i == n-1) return 1;
    int& ret = cache[c][i];
    if (ret != -1) return ret;
    ret = 0;
    if (c == 2)
        ret = (search(0, i) + 2 * search(1, i)) % 9901;
    else if (c == 1)
        ret = (search(0, i + 1) + search(1, i + 1)) % 9901;
    else if (c == 0)
        ret = (2 * search(1, i + 1) + search(0, i + 1)) % 9901;
    return ret;
}
int main(){
    memset(cache, -1, sizeof(cache));
    scanf("%d", &n);
    printf("%d", n == 1 ? 3 : (search(2, 0)%9901));
}