kmjp's blog

競技プログラミング参加記です

yukicoder : No.616 へんなソート

これはもうひとひねりしてもよかったのでは。
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;
}

まとめ

同じ要素が含まれていても面白かったと思いますけどね。