本番つめが甘くて時間内に終えられなかった。
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だけど、コードは何気に短い。