これはもうひとひねりしてもよかったのでは。
https://yukicoder.me/problems/no/616
問題
各要素がdistinctなN要素の数列が与えられる。
この数列のpermutationのうち、転倒数がK以下の物はいくつあるか。
解法
各要素はdistinctなので、0~(N-1)を並べ替えると考えても問題ない。
小さい順に要素を挿入していくことを考える。
(i-1)までの要素の並びが決まっているとき、要素iの挿入位置を決める場合は、転倒数が0~i増加するような候補が考えられる。
よって、f(n,k) := n要素のpermutationのうち転倒数がkの物の組み合わせ数 とすると
- f(*,0) := 1
- f(n,k) := sum_{i=0..(n-1)} f(n-1,k-i)
と計算できる。
累積和を使えばO(NK)で回答可能。
int N,K; ll from[100300]; ll S[100300]; ll to[100300]; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; from[0]=1; FOR(i,N) { FOR(j,100000) { S[j+1]=(S[j]+from[j])%mo; to[j]=(S[j+1]-(j-i>=0?S[j-i]:0)+mo)%mo; } swap(from,to); } ll ret=0; FOR(i,K+1) ret+=from[i]; cout<<ret%mo<<endl; }
まとめ
同じ要素が含まれていても面白かったと思いますけどね。