테스트

수식

$$ d_{i j}=d_{i-1 j}+d_{i j-1} $$

#include <bits/stdc++.h> using namespace std; long long dp[33339][3]; const long long MOD = 1e9+9; int main() { int n; scanf("%d",&n); dp[0][0] = 1LL; for(int i=1; i<=n; i++) { if(i!=1) dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; dp[i][1] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]; dp[i][0] %= MOD; dp[i][1] %= MOD; dp[i][2] %= MOD; } printf("%lld", dp[n][0]); return 0; }