Codeforce 1000 D. Yet Another Problem On a Subsequence 解析(DP)

今天我們來看看CF1000D
題目連結

題目
略，請直接看原題

前言

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

想法

考慮$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