[ABC242] C - 1111gal password

[Q] https://atcoder.jp/contests/abc242/tasks/abc242_c

DP[index][1~9] = 何通り で管理する。
1. 初期条件は？
2. 遷移は？
3. 解答は？

1. 初期条件は？
DP[0][1]=1
DP[0][2]=1
DP[0][3]=1
DP[0][4]=1
DP[0][5]=1
DP[0][6]=1
DP[0][7]=1
DP[0][8]=1
DP[0][9]=1

2. 遷移は？
DP[1][1]=2 //            DP[0][1] + DP[0][2]
DP[1][2]=3 // DP[0][1] + DP[0][2] + DP[0][3]
DP[1][3]=3 // DP[0][2] + DP[0][3] + DP[0][4]
DP[1][4]=3 // DP[0][3] + DP[0][4] + DP[0][5]
DP[1][5]=3 // DP[0][4] + DP[0][5] + DP[0][6]
DP[1][6]=3 // DP[0][5] + DP[0][6] + DP[0][7]
DP[1][7]=3 // DP[0][6] + DP[0][7] + DP[0][8]
DP[1][8]=3 // DP[0][7] + DP[0][8] + DP[0][9]
DP[1][9]=2 // DP[0][8] + DP[0][9]

3. 解答は？

もし N=2 なら
ans = DP[1][1~9] の総和

実装

mint DP[1000010][11]; // 0と10 はすてる
int main(){
  cincout();
  
  ll N;
  cin >> N;
  
  // 初期入れ
  rep(i, 11) DP[0][i] = 1;
  // DP
  rep(i, N-1){
    for(ll j=1; j<=9; ++j){
      for(ll k=-1; k<=1; ++k){
      // もらうDP
        DP[i+1][j+k] += DP[i][j];
      }
    }
  }
  mint ans = 0;
  // 解答はDP[N-1]の総和
  for(ll i=1; i<=9; ++i){
    ans += DP[N-1][i];
  }
  cout << ans << endl;
}

https://atcoder.jp/contests/abc242/submissions/29892523