---
title: Codeforce 1000 D. Yet Another Problem On a Subsequence 解析(DP)
description: "Codeforce 1000 D. Yet Another Problem On a Subsequence 解析(DP)"
disqus: hackmd
---
<meta name="robots" content="Codeforce 1000 D. Yet Another Problem On a Subsequence 解析(DP)">
<!-- toc -->

# Codeforce 1000 D. Yet Another Problem On a Subsequence 解析(DP)
今天我們來看看CF1000D
[題目連結](https://codeforces.com/problemset/problem/1000/D)

> **題目**
略，請直接看原題

### 前言
這題提供了我一種實用的算$C_m^n$的方法

<div class="VVVcopyrightAAA";>@copyright petjelinux 版權所有<br>
<a href="https://www.cnblogs.com/petjelinux/">觀看更多正版原始文章請至petjelinux的blog</a></div>

### 想法
考慮$dp[i]$為考慮到$i$位置為止的所以$subsequence$數量$+1$(一個都不選)，解答就是$dp[n]-1$。
每次新考慮一個$dp[i]$時，$dp[i]$由不包含$a[i]$($a$是原數列)的$subsequence$數量加上包含$a[i]$的$subsequence$數量。而考慮包含$a[i]$的數量時，我們只需要往前找最後一個$subarray$的起點($a[j]>0$)，接著使用$C_m^n$找出最後的$subarray$有幾種可能就好。

重點在於要如何計算$C_m^n$，數字太容易爆掉了。這時候我們要利用$C_m^n=C_m^{n-1}+C_{m-1}^{n-1}$，這樣就不會爆掉了，並且要特別令$C_0^0=1$，因為我們之後計算$dp$時會用到。

轉移式$:dp[i]=dp[i-1]+\sum\limits_{j=1}^{i-1}dp[j-1]\times C_{a[j]-1}^{i-j-1}$

注意:我們令$dp[0]=1$以方便計算。而數列標號是從$1$開始。
### 程式碼:

inline int pmod(int x, int d){int m = x%d;return m+((m>>31)&d);}
const int _n=1010;
int t,n,a[_n],dp[_n],C[_n][_n];
main(void) {cin.tie(0);ios_base::sync_with_stdio(0);
  cin>>n;rep(i,1,n+1)cin>>a[i];
  rep(i,1,n+1){
    C[i][0]=C[i][i]=1;
    rep(j,1,i)C[i][j]=(1ll*C[i-1][j]+1ll*C[i-1][j-1])%mod;
  }C[0][0]=1;
  dp[0]=dp[1]=1;
  rep(i,2,n+1){
    dp[i]=dp[i-1];
    per(j,1,i)
      if(a[j]>0 and a[j]<=i-j)dp[i]=(dp[i]+(1ll*dp[j-1]*C[i-j-1][a[j]-1]))%mod;
  }
  cout<<pmod(dp[n]-1,mod)<<'\n';
  return 0;
}

標頭、模板請點Submission看
[Submission](https://codeforces.com/contest/1000/submission/92117053)