結果

問題 No.271 next_permutation (2)
コンテスト
ユーザー vjudge1
提出日時 2026-01-27 11:14:45
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 2,195 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,044 ms
コンパイル使用メモリ 215,440 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-27 11:14:49
合計ジャッジ時間 3,737 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define LL long long

#define N 100007
#define mod 1000000007
int a[N],jc[N]={1},f[N];
LL jc_[21]={1};

int n,t[N];
inline void Add(int x,int v){for(;x<=n;x+=x&-x) t[x]+=v;}
inline int Sum(int x){int s=0;for(;x;x-=x&-x) s+=t[x];return s;}

int PreAns(LL k){
	int Ans=0;
	for(int i=20;i;i--){
		LL mtp=jc_[i-1];
		int p=k/mtp;k%=mtp;
		Ans=(Ans+p*(p-1)/2*1ll*(mtp%mod)%mod)%mod;
		Ans=(Ans+p*1ll*f[i-1]%mod)%mod;
		Ans=(Ans+(k%mod)*p%mod)%mod;
	}
	return Ans;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	LL k,Ans0=0;
	cin>>n>>k;
	if(!k) {cout<<0<<'\n';return 0;}
	for(int i=1;i<=n;i++) cin>>a[i],Ans0+=(i-1)-Sum(a[i]-1),Add(a[i],1);
	jc[1]=jc_[1]=1;
	for(int i=2;i<=20;i++) jc_[i]=jc_[i-1]*i,f[i]=(i*1ll*f[i-1]%mod+i*1ll*(i-1)/2%mod*1ll*(jc_[i-1]%mod)%mod)%mod;
	
	k--;int Ans=Ans0%mod;
	if(!k) {cout<<Ans<<'\n';return 0;}
	for(int i=n-1;i;i--){
		Add(a[i+1],-1);
		int now=(a[i]-1)-Sum(a[i]-1);//?a[i]??a[i]?????? 
		Ans0-=now;
		if(now==n-i) continue;//??????????? 
		if(n-i>=20){//20!???? 
			Ans0+=now+1;
			int last=(k%mod)*(Ans0%mod)%mod;
			Ans=(Ans+last)%mod;
			Ans=(Ans+PreAns(k))%mod;
			cout<<Ans<<'\n';
			return 0;
		}
		LL prs=jc_[n-i+1]-(now+1)*jc_[n-i];//?????? 
		if(k<prs){//????? 
			Ans=(Ans+(k%mod)*(Ans0%mod)%mod)%mod;//a[i]????? 
			int tmp=k/jc_[n-i],tmp2=0;
			for(int j=now+1;j<=now+tmp;j++) tmp2+=j;//a[i]?????? 
			tmp2=tmp2*1ll*(jc_[n-i]%mod)%mod;//??(n-i)!? 
			Ans=(Ans+tmp2)%mod;tmp2=0;//a[i]????? 
			Ans=(Ans+tmp*1ll*f[n-i]%mod);//a[i]??????? 
			k%=jc_[n-i];int now2=now+tmp+1;
			if(k) Ans=(Ans+now2*k%mod)%mod,//a[i]?????? 
				Ans=(Ans+PreAns(k))%mod;//a[i]??????? 
			cout<<Ans<<'\n';return 0;
		}
		k-=prs;
		Ans=(Ans+(prs%mod)*(Ans0%mod)%mod)%mod;//a[i]???????? 
		int Minus=((now+1)*1ll*f[n-i]%mod+now*(now+1)/2*1ll*(jc_[n-i]%mod)%mod)%mod;
		int Now=(f[n-i+1]+mod-Minus)%mod;//a[i]????? 
		Ans=(Ans+Now)%mod;//cout<<i<<' '<<prs<<'-'<<Ans<<'\n';
		if(!k){cout<<Ans<<'\n';return 0;}
	}
	if(n<=20){
		LL cyc=k/jc_[n];
		k%=jc_[n];
		Ans=(Ans+(cyc%mod)*f[n]%mod)%mod;
	}
	if(k) Ans=(Ans+PreAns(k))%mod;
	cout<<Ans<<'\n';
	
	return 0;
}
/*
5 10
4 3 2 5 1

10 100
2 4 6 9 10 8 1 5 7 3
*/
0