正題

題目鏈接:https://www.luogu.org/problemnew/show/P2513

---

題目大意

求長度為$n$逆序對為$k$個的序列總數。

---

解題思路

設$f_{i,j}$表示$1～i$的排列逆序對個數為$j$
然后顯然:$$f_{i,j}=\sum _{k=1}^{i?1}{f}_{i?1,j?k}$$
前綴和優化

---

$code$rtf

#include<cstdio> #include<algorithm> using namespace std; int n,k,f[1100][1100]; int main() {scanf("%d%d",&n,&k);f[1][0]=1;for(int i=2;i<=n;i++){for(int j=0;j<=k;j++)(f[i-1][j]+=f[i-1][j-1])%=10000;for(int j=0;j<=k;j++)f[i][j]=(f[i-1][j]-f[i-1][max(0,j-i+1)-1]+10000)%10000;}printf("%d",f[n][k]); }

總結

以上是生活随笔為你收集整理的P2513-[HAOI2009]逆序对数列【dp,前缀和】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。