結果

問題 No.271 next_permutation (2)
ユーザー hjxhjx
提出日時 2025-05-24 18:20:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 8 ms / 2,000 ms
コード長 1,578 bytes
コンパイル時間 1,378 ms
コンパイル使用メモリ 163,620 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-24 18:20:40
合計ジャッジ時間 2,519 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ll long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

inline static ll read(){
    ll sum=0; int ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) sum=sum*10+(ch^48),ch=getchar();
    return sum;
}

constexpr int mod=1e9+7;
int n,a[100005],arr[100005]; ll fac[21]; ll Fac(int n){return fac[min(n,20)];}
void update(int p){for(;p<=n;p+=p&-p) arr[p]++;}
int query(int p,int ret=0){for(;p;p^=p&-p) ret+=arr[p]; return ret;}
ll f(int n){return Fac(n)/2%mod*(n*(n-1ll)/2%mod)%mod;}
ll calc(ll k,ll ret=0,int n=1){
    while(k>=Fac(n)) n++; n--;
    for(int i=n,t;~i;i--){
        ll _f=Fac(i); t=k/_f,k-=t*_f;
        ret=(ret+t*(t-1ll)/2*(_f%mod)+t*(f(i)+k))%mod;
    } return ret;
}
signed main(){
    // freopen("inversion.in","r",stdin);
    // freopen("inversion.out","w",stdout);
    n=read(),*fac=1; ll k=read()-1,_k=k+1,zk=0,Ans=0; int p=0,rk_p=0;
    for(int i=1;i<21;i++) fac[i]=fac[i-1]*i;
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=n,x;i>=1;update(a[i--])){
        ll _f=Fac(n-i); x=query(a[i]),Ans=(Ans+(_k-k)%mod*x)%mod;
        if(k) if(k<(__int128)(n-i-x)*_f) p=i,zk=k,k=0,rk_p=x;
        else Ans=(Ans+(x+1ll+n-i)*(n-i-x)/2%mod*(_f%mod)+(n-i-x)*f(n-i))%mod,k-=(n-i-x)*_f;
    }
    if(p){
        ll _f=Fac(n-p); int x=rk_p,t=zk/_f; zk-=t*_f;
        Ans=(Ans+(2*x+t+1ll)*t/2%mod*(_f%mod)+zk%mod*(x+t+1ll)+t*f(n-p)+calc(zk))%mod;
    }else{
        ll t=k/Fac(n)*Fac(n);
        Ans=(Ans+t/2%mod*(n*(n-1ll)/2%mod)+calc(k-t))%mod;
    } return printf("%lld\n",Ans),0;
}
0