提供一个不用期望的做法。
考虑一个区间 \([l,r]\) 的贡献,就是这段区间的和乘上有多少排列的权值要用到这段区间。
现在讨论有多少排列的权值有这段区间。
这段区间会被用到当且仅当 \(l-1\) 和 \(r+1\) 均出现在 \(l\sim r\) 的前面,即把这个区间分裂出来。
为了避免出错,这里进行分类讨论:
- 如果这个区间靠边,则仅需要 \(l-1\) 或 \(r+1\) 在前面,个数为 \(\frac{n!}{len+1}\)(\(len\) 为区间长度)。
- 如果这个区间不靠边,则需要 \(l-1\) 或 \(r+1\) 都在区间前面出现,个数为 \(\frac{2n!}{(len+1)(len+2)}\)。
关于这个式子的理解:
先只考虑 \(l-1\),方案数为 \(\frac{n!}{len+1}\),现在对于 \(l-1\) 和这个区间的合法排列(即 \(l-1\) 出现在区间前面),\(r+1\) 有 \(len+2\) 种放法插入期间,其中合法的只有 \(2\) 种,即放在 \(l-1\) 的前面或者后面,相当于每 \(len+2\) 种方案取 \(2\) 种方案。
容易发现,这个方案数只跟区间长度及是否靠边有关,与区间的位置无关,因此现在只需要统计长度为 \(len\) 的区间的权值和,这是比较容易的,考虑每个数在长为 \(len\) 的线段从左往右滑的过程中被覆盖几次,很容易预处理。
所以枚举区间长度统计答案就行了。
细节:
- 长度为 \(n\) 的区间单独讨论。
- 在统计长度为 \(len\) 的答案时是否靠边也要讨论。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define eb(x) emplace_back(x)
const int mod=1e9+7,N=1e5+10;
typedef long long LL;
typedef pair<int,int> pii;
template<typename T>inline void read(T &x)
{
int f=1;
x=0;
char c=getchar();
while(!isdigit(c))
{
if(c=='-') f=-1;
c=getchar();
}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f;
}
template<typename T,typename ...L>inline void read(T &x,L &...l){read(x),read(l...);}
template<typename T>inline void print(T x)
{
if(x<0) putchar('-'),x=-x;
char c[30];
int t=0;
do{
c[t++]=x%10+'0',x/=10;
}while(x);
while(t) putchar(c[--t]);
putchar('\n');
}
template<typename T,typename ...L>inline void print(T x,L ...l){print(x),print(l...);}
template<typename T,typename L>inline void chkmx(T &x,L y){(x<y) && (x=y);}
template<typename T,typename L>inline void chkmn(T &x,L y){(x>y) && (x=y);}
int inc(const int &a,const int &b){return a+b>=mod?a+b-mod:a+b;}
int dec(const int &a,const int &b){return a-b<0?a-b+mod:a-b;}
int mul(const int &a,const int &b){return 1ll*a*b%mod;}
int sqr(const int &a){return 1ll*a*a%mod;}
void Inc(int &a,const int &b){a=a+b>=mod?a+b-mod:a+b;}
void Dec(int &a,const int &b){a=a-b<0?a-b+mod:a-b;}
void Mul(int &a,const int &b){a=1ll*a*b%mod;}
void Sqr(int &a){a=1ll*a*a%mod;}
int qmi(int a,int b)
{
int res=1;
while(b)
{
if(b&1) Mul(res,a);
Sqr(a),b>>=1;
}
return res;
}
int n,a[N],s[N],b[N],ans,fac[N],infac[N];
void init()
{
fac[0]=infac[0]=1;
for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
infac[n]=qmi(fac[n],mod-2);
for(int i=n;i>=1;i--)
infac[i-1]=mul(infac[i],i);
}
int main()
{
read(n);
init();
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=n/2;i++) b[i]=inc(b[i-1],mul(i,inc(a[i],a[n-i+1])));
for(int i=1;i<=n;i++) s[i]=inc(s[i-1],a[i]);
ans=mul(fac[n],s[n]);
//Inc(ans,inc(mul(fac[n-1],s[n-1]),mul(fac[n-1],dec(s[n],s[1]))));
for(int i=1;i<=n-1;i++)
{
int cnt=mul(mul(2,fac[n]),mul(qmi(i+1,mod-2),qmi(i+2,mod-2)));
int lim=min(i,n-i+1)-1;
int ss=dec(inc(b[lim],mul(lim+1,dec(s[n-lim],s[lim]))),inc(s[i],dec(s[n],s[n-i])));
Inc(ans,mul(cnt,ss));
Inc(ans,inc(mul(s[i],mul(fac[n],qmi(i+1,mod-2))),mul(dec(s[n],s[n-i]),mul(fac[n],qmi(i+1,mod-2)))));
}
cout<<ans<<endl;
return 0;
}
标签:AGC028B,const,int,void,len,read,区间
From: https://www.cnblogs.com/cooltyl/p/17972380