2018牛客网暑期ACM多校训练营（第一场）F:Sum of Maximum

题意：给定N个数a[]，现在用a形成一个新的数组b[]，1<=b[i]<=a[i]。问所有的方案的最大值之和。

思路：先排序。然后分段统计贡献，假设a[i-1]<a[i]，那么[a[i-1]+1,a[i]]的贡献就是左边的所有方案*右边的合法方案，合法即是最大值这个区间内。

假设max=x，那么右边的贡献是x*(x^(n-i+1)-(x-1)*(n-i+1)); 所有的x加起来，发现是个前缀和，=x^(n-i+2)+(x-1)^(n-i+1)+...^(n-i+1)；最右边部分可以用拉格朗日求出。

所有就完了。但是我的板子好像有点慢。

（毕竟我多加了一个log，明天来修改一下。今天还有几个题要补。

（实则是在准备板子。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=200010;
const int Mod=1e9+7;
const int mod=1e9+7;
int a[maxn],sum[maxn],ans;
ll f[maxn],fac[maxn],inv[maxn];
ll P(ll a,ll b)
{
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%mod;
        b>>=1; a=a*a%mod;
    }
    if(ans<0) ans+=mod;
    return ans;
}
void init(int tot)
{
    fac[0]=1;
    for(int i=1;i<=tot;i++)
        fac[i]=fac[i-1]*i%mod;
    inv[tot]=P(fac[tot],mod-2);
    inv[0]=1; //求阶乘逆元
    for(int i=tot-1;i>=1;i--)
        inv[i]=inv[i+1]*(i+1)%mod;
}
ll Lagrange(ll n,ll k)
{
    rep(i,1,k+1) f[i]=(f[i-1]+P(i,k-1))%mod;
    if(n<=k+1) return f[n];
    int tot=k+1; init(tot);
    ll ans=0,now=1;
    for(int i=1;i<=tot;i++) now=now*(n-i)%mod;
    for(int i=1;i<=tot;i++) {
        ll inv1=P(n-i,mod-2);
        ll inv2=inv[i-1]*inv[tot-i]%mod;
        if((tot-i)&1) inv2=mod-inv2;
        ll temp=now*inv1%mod;
        temp=temp*f[i]%mod*inv2%mod;
        ans+=temp;
        if(ans>=mod) ans-=mod;
    }
    return ans;
}
int solve(int x,int k)
{
    if(!x) return 0;
    return P(x,k+1)-Lagrange(x-1,k+1);
}
int main()
{
    int N;
    while(~scanf("%d",&N)){
        rep(i,1,N) scanf("%d",&a[i]);
        sort(a+1,a+N+1); ans=0; sum[0]=1;
        rep(i,1,N) sum[i]=1LL*sum[i-1]*a[i]%Mod;
        rep(i,1,N) {
            if(a[i]==a[i-1]) continue;
            int res=(solve(a[i],N-i+1)-solve(a[i-1],N-i+1)+Mod)%Mod;
            (ans+=1LL*sum[i-1]*res%Mod)%=Mod;
        }
        printf("%d
",ans);
    }
    return 0;
}

2018牛客网暑期ACM多校训练营（第一场）F:Sum of Maximum

相关推荐