description
一个长度为 \(n\) 的排列 \(a\)，其权值为满足 \(a_i>i\) 的位置的数量。
求权值恰为 \(k\) 的长度为 \(n\) 的排列的方案数。
- \(n,k\leq 1000\)
solution
设 \(f_{i,j}\) 表示考虑前 \(i\) 个数，钦定 \(j\) 个满足 \(a_i>i\)，这 \(j\) 个数排列的方案数。有转移：
-
\(f_{0,0}=1\)
-
\(f_{i,j}=f_{i-1,j}+(i-j)f_{i-1,j-1}\)
剩下的 \(n-j\) 个数随便排，乘个阶乘就行，然后再二项式反演。