ABC 178 C - Ubiquity 解説 【別解】

atcoder.jp

解説

想定解は包除原理だが、Nが小さいので動的計画法でも間に合う。

dp[i][j][k] := i桁目まで確定していて、0を使ったかがj、9を使ったかがkである状態のときの通り数

dpテーブルをこのように定義すると、テーブル更新にかかる計算量は、O(N * 2 * 2 * 10) となるので十分間に合う。

実装

ll dp[1000005][2][2];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n; cin>>n;
  
  dp[0][0][0]=1;
  
  rep(i,n){
    rep(j,2){
      rep(k,2){
        rep(l,10){
          ll nj=j, nk=k;
          if(l==0) nj=1;
          if(l==9) nk=1;
          (dp[i+1][nj][nk]+=dp[i][j][k])%=MOD;
        }
      }
    }
  }
  
  ll ans=dp[n][1][1];
  cout<<ans<<endl;
  
}

まとめ

ABCはたまにこんな脳死DPが使える気がする。