atcoder ABC 178 C - Ubiquity

AtCoder DP

問題

C - Ubiquity

公式解説にある通り、包除原理を理解していれば数行で解ける問題。

包除原理にたどり着けず納得が行かなかったので公式解説動画で言及されていたDP解法で解いてみた。

DP解法

DPは [N][0を含んでいるかどうか][9を含んでいるかどうか] で取る。

4重ループで数え上げていき、dp[n][1][1] が最終的に長さnで0,9を含む数列の数となる。

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0;i<n;i++)
using ll = long long;
const int MOD = 1e9+7;

int n;
int dp[1000010][2][2]; // [N][0を含むかどうか][9を含むかどうか]

// DP解法
void solve() {
  dp[0][0][0] = 1;
  REP(i,n) {
    REP(j,2) {
      REP(k,2) {
        REP(x,10) {
          int nj = j | x == 0;
          int nk = k | x == 9;
          dp[i+1][nj][nk] += dp[i][j][k];
          dp[i+1][nj][nk] %= MOD;
        }
      }
    }
  }
  cout << dp[n][1][1] << endl;
}

int main() {
  cin >> n;
  solve();

  return 0;
}