동물원

#include<cstdio>

using namespace std;

unsigned long long a[100001][3];
unsigned long long d[100001][4];

int n;

int main(){
    scanf("%d", &n);

    d[1][1] = 1;
    d[1][2] = 1;
    d[1][3] = 1;
    for(int i = 2; i <= n; i++){
        d[i][1] = d[i-1][2] + d[i-1][3];
        d[i][1] %= 9901;
        d[i][2] = d[i-1][1] + d[i-1][3];
        d[i][2] %= 9901;
        
        d[i][3] = d[i-1][1]+d[i-1][2]+d[i-1][3];
        d[i][3] %= 9901;

    }
    unsigned long long sun = 0;
    sun = (d[n][1] + d[n][2] + d[n][3]) %9901;
    printf("%lld", sun);
    return 0;
}

역시 굉장히 쉬운 DP문제 

근데 모듈로 연산은 할때마다 헷갈린다 외워야할듯

값이 좀커질거같아서 역시나 unsigned long long 타입으로 진행함