首页 > 其他分享 >AGC028B

AGC028B

时间:2024-01-18 14:13:11浏览次数:21  
标签:AGC028B const int void len read 区间

提供一个不用期望的做法。
考虑一个区间 \([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

相关文章

  • [AGC028B] Removing Blocks
    E-EternalAverage真的好做这道题的时候严重怀疑自己发烧了,不知道为什么,感觉身上冷冰冰的,头还烫烫的,有可能是因为太闷了,导致脑子有点不够用性质推简单dp了令最后留下......