出题人题解 | #序列上问题#

原题解链接：https://ac.nowcoder.com/discuss/163610

题目大意 请你求出一个$11$ ~ $NN$的排列，使得它正好有$KK$个逆序对。

由于存在很多种这样的排列，所以要求出字典序最大的排列。

因为排列可能很长，所以你只用输出类似于将这个排列放到$N+1N+1$ 进制下的值，即 ${\sum }_{i=1}^{N}p[i]\ast (N+1{)}^i\mathrm{m}\mathrm{o}\mathrm{d}10^9+7\backslash sum\; \backslash limits\; \_\{i=1\}^\{N\}\; p[i]*(N+1)^i\; \backslash mod\; \backslash \; 10^9+7$，其中 $pp$ 是你求出的排列。

题目分析 观察字典序最大的排列，发现由四段组成：

第一段是一段从 $NN$开始的连续下降序列（也可能没有）。

第二段是一个单独的数字。

第三段是一段从 $11$ 开始的连续上升序列。

第四段的开头是第三段的结尾 $+2+2$，略过的数字正好是第二段。

可以二分出第二段那个数字是多少，然后其它三段都是数列求和。

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

int n;
ll k;
const ll p=1e9+7;
ll calc(int l,int r){
	return 1LL*(r+l)*(r-l+1)/2;
}
ll pw(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)
			ret=ret*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ret;
}
int main(){
	scanf("%d%lld",&n,&k);
	int l=0,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(calc(n-mid,n-1)<=k)
			l=mid+1;
		else
			r=mid;
	}
	if(calc(n-l,n-1)>k)
		l--;
	ll x=(n+1)%p,ans1=(-1LL*n*x%p+(pw(x,l+1)-pw(x,2)+p)%p*pw(x-1,p-2)%p+1LL*(n-l+1)*pw(x,l+1)%p+p)%p*pw(x-1,p-2)%p;
	k-=calc(n-l,n-1)-1;
	ll ans2=k%p*pw(x,l+1)%p,ans3=((pw(x,l+k+1)-pw(x,l+2)+p)%p*pw(x-1,p-2)%p-(k-1)%p*pw(x,l+k+1)%p+p)%p*pw((1-x+p)%p,p-2)%p;
	ll ans4=((k+1)%p*pw(x,l+k+1)%p-1LL*(n-l)%p*pw(x,n+1)%p+(pw(x,n+1)-pw(x,l+k+2)+p)%p*pw(x-1,p-2)%p+p)%p*pw((1-x+p)%p,p-2)%p;
	printf("%lld\n",(ans1+ans2+ans3+ans4)%p);
	return 0;
}