yukicoder : No.645 Count Permutation

本番つめが甘くて時間内に終えられなかった。
https://yukicoder.me/problems/no/645

問題

N要素の数列Bに対し、以下の処理を順次行った結果をf(B)とする。

• i=0～(N-2)に対し、B[i]＞B[i+1]なら両者をスワップする。

g(A)を、Aに対しf(B)=AとなるBの数とする。

整数N,L,Rが与えられる。
1～NのPermutationであるAのうち、g(A)がL以上R以下となるものは何通りあるか。

解法

こちらも小さい要素数で試してみよう。
すると、g(A)は以下のようになる。

• 最大値Nが最後尾に無い場合0
• それ以外の場合、A[0]～A[i]中でA[i]が最大となるiの数がp個ある場合、2^(p-1)

N!通りのPermutation中、前者はN!-(N-1)!通りなので、L==0のときはその分を解に加える。
H(p)を上記の定義における数え方でp個となるAの数とすると、L≦2^(p-1)≦Rとなるpの間でH(p)の数を数えればよい。

Aのうち最後尾は最大値Nで決まりだが、残り(N-1)要素は(N-1)!通りの並びがある。
要素を大きい順に数列に追加することを考えると、先頭に要素を加えたときのみpが増える。
よって各要素が先頭に追加される確率を適宜挿入DPの要領で考えるとH(p)はO(Np)で求めることができる。
Rが10^18なので、pは60程度まで数えればよい。

ll N,L,R;
ll mo=1000000007;
ll fact[101010];
ll dp[70];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=100100;i++) fact[i]=fact[i-1]*i%mo;
	
	cin>>N>>L>>R;
	dp[1]=1;
	for(i=2;i<=N-1;i++) {
		for(j=65;j>=1;j--) {
			(dp[j+1]+=dp[j])%=mo;
			(dp[j]*=i-1)%=mo;
		}
	}
	ll ret=0;
	for(i=1;i<=61;i++) if(L<=(1LL<<i) && (1LL<<i)<=R) ret+=dp[i];
	if(L==0) ret+=mo+fact[N]-fact[N-1];
	cout<<ret%mo<<endl;
}

まとめ

★4.5だけど、コードは何気に短い。