牛客月赛60 F.被抓住的小竹(数学&推式子)

考虑枚举每个区间的贡献。

每个区间内所有的数都作为xxx一次时的贡献和。

因为要求区间内≥x\ge x≥x数个数， 那么区间内的数从小到大排序后，显然最大的数贡献是1、第二大的数贡献是2，依此内推。

因此对于长度为lenlenlen的贡献是∑i=1leni=len(len+1)2\sum_{i=1}^{len}i=\dfrac{len(len+1)}{2}∑i=1len​i=2len(len+1)​

因此我们可以枚举区间长度。

区间长度为iii的个数为n−i+1n-i+1n−i+1。

所以总贡献是：∑i=1n(n−i+1)×i(i+1)2\sum\limits_{i=1}^n(n-i+1)\times \dfrac{i(i+1)}{2}i=1∑n​(n−i+1)×2i(i+1)​然后展开化简一波。

ans=n(n+1)(n+2)(n+3)24ans=\dfrac{n(n+1)(n+2)(n+3)}{24}ans=24n(n+1)(n+2)(n+3)​

是一个组合数的形式：ans=Cn+34ans=C_{n+3}^4ans=Cn+34​与排列无关。

因此可以提出来，然后res=ans×∑pinv(p)res=ans\times\sum_pinv(p)res=ans×∑p​inv(p)

求所有排列的逆序对和，可以这样考虑。

一共有n!n!n!个排列，对于一个两个数i,j(iposjpos_i>pos_jposi​>posj​。因此贡献是n!2\dfrac{n!}{2}2n!​。

所有有序对总数是n(n−1)2\dfrac{n(n-1)}{2}2n(n−1)​

所以答案就是：Cn+34n!n(n−1)4=n2×(n+3)!×(n−1)96C_{n+3}^4\dfrac{n!n(n-1)}{4}=\dfrac{n^2\times (n+3)!\times(n-1)}{96}Cn+34​4n!n(n−1)​=96n2×(n+3)!×(n−1)​

#include
using namespace std;
int mod=1e9+7;
long long power(long long a,long long b){long long res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;
}
long long inv(int x){return power(x,mod-2);
}
long long jc[2020200];
int main(){jc[0]=1;int n,i,j,k;for(i=1;i<=1e5+10;i++)jc[i]=jc[i-1]*i%mod;cin>>k;while(k--){long long x;cin>>x;cout<