毒瘤 jxd 作业……
首先我们不能直接对所有排列计算贡献对吧,这样复杂度肯定吃不消,因此我们考虑对每两个位置 \(x,y(x
\[C=\prod\limits_{i=1}^n(b_i-i+1)
\]
我们考虑从这个性质入手计算符合要求的排列个数。对于一对 \((i,j)(i
\[C'=C·\dfrac{a_i-r_i}{a_j-r_j+1}·\prod\limits_{k=r_i+1}^{r_j-1}\dfrac{b_k-k}{b_k-k+1}
\]
考虑怎样求解这个东西,我们按照排名 \(r_i\) 从小到大枚举 \(a_i\),即按照 \(b_1,b_2,\cdots,b_n\) 的顺序枚举这些限制,在访问过程中可以维护一个序列 \(c\),当我们访问到一个 \(i\) 时就令 \(c_i=b_i-i\),然后每次访问完 \(i\) 就将 \(c_1,c_2,\cdots,c_{i-1}\) 全部乘上 \(\dfrac{b_i-i}{b_i-i+1}\),那么可以发现,如果我们记 \(N(x,y)\) 表示当 \(r_i=x,r_j=y\) 时上式中 \(C’\) 的值,那么 \(N(x,y)\) 就等于,我们访问到 \(x\) 时,\(C·\dfrac{1}{b_y-y+1}·c_x\) 的值。故设 \(p_i\) 满足 \(p_{r_i}=i\),那么访问到 \(y\) 时的贡献就是 \(\prod\limits_{p_x<p_y}N(x,y)=C·\dfrac{1}{b_y-y+1}·\sum\limits_{p_x<p_y}c_x\),这个可以通过维护一个全局乘+单点更新+区间求和的线段树解决。
当然这仅仅只是 \(a_i<a_j\) 的 \((i,j)\) 的贡献。对于 \(a_i\ge a_j\) 的情况也大同小异,我们考虑拿总排列数 \(C\) 减去 \(p_i<p_j\) 的排列个数,后者只需把序列翻转过来再做一遍上述操作即可。
时间复杂度 \(n\log n\)。
注:以下代码中 \(a_i\ge a_j\) 部分的处理方法与题解略有差异,它并没有按照题解所述将序列翻转过来重复 \(a_i<a_j\) 部分的过程,而是在第一遍扫描线过程中一并算出 \(a_i\ge a_j\) 的答案。
const int MAXN=2e5;
const int MOD=1e9+7;
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int n;
struct data{
int val,id;
data(int _val=0,int _id=0):val(_val),id(_id){}
bool operator <(const data &rhs){return val<rhs.val;}
} a[MAXN+5];
struct node{int l,r,val,lz;} s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;s[k].lz=1;if(l==r) return s[k].val=0,void();
int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushdown(int k){
if(s[k].lz^1){
s[k<<1].val=1ll*s[k<<1].val*s[k].lz%MOD;
s[k<<1].lz=1ll*s[k<<1].lz*s[k].lz%MOD;
s[k<<1|1].val=1ll*s[k<<1|1].val*s[k].lz%MOD;
s[k<<1|1].lz=1ll*s[k<<1|1].lz*s[k].lz%MOD;
s[k].lz=1;
}
}
void tag_mul(int x){
s[1].lz=1ll*s[1].lz*x%MOD;
s[1].val=1ll*s[1].val*x%MOD;
}
int query(int k,int l,int r){
if(l>r) return 0;
if(l<=s[k].l&&s[k].r<=r) return s[k].val;
pushdown(k);int mid=s[k].l+s[k].r>>1;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%MOD;
}
void modify(int k,int p,int x){
if(s[k].l==s[k].r) return s[k].val=x,void();
pushdown(k);int mid=s[k].l+s[k].r>>1;
(p<=mid)?modify(k<<1,p,x):modify(k<<1|1,p,x);
s[k].val=(s[k<<1].val+s[k<<1|1].val)%MOD;
}
int t[MAXN+5];
void add(int x,int v){for(int i=x;i;i&=(i-1)) t[i]+=v;}
int query(int x){int ret=0;for(int i=x;i<=n;i+=(i&(-i))) ret+=t[i];return ret;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].val),a[i].id=i;
sort(a+1,a+n+1);int tot=1,res=0;
for(int i=1;i<=n;i++) tot=1ll*tot*(a[i].val-i+1)%MOD;
if(!tot) return puts("0"),0;build(1,1,n);
for(int i=1;i<=n;i++){
res=(res+1ll*qpow(2*(a[i].val-i+1),MOD-2)*query(1,1,a[i].id-1))%MOD;
res=(0ll+res+query(a[i].id)-1ll*qpow(2*(a[i].val-i+1),MOD-2)*query(1,a[i].id+1,n)%MOD+MOD)%MOD;
tag_mul(1ll*(a[i].val-i)*qpow(a[i].val-i+1,MOD-2)%MOD);
modify(1,a[i].id,a[i].val-i);add(a[i].id,1);
} printf("%d\n",1ll*res*tot%MOD);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章