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=;

const int Mod=1e9+;

const int mod=1e9+;

int a[maxn],sum[maxn],ans;

ll f[maxn],fac[maxn],inv[maxn];

ll P(ll a,ll b)

{

    ll ans=;

    while(b) {

        if(b&) ans=ans*a%mod;

        b>>=; a=a*a%mod;

    }

    if(ans<) ans+=mod;

    return ans;

}

void init(int tot)

{

    fac[]=;

    for(int i=;i<=tot;i++)

        fac[i]=fac[i-]*i%mod;

    inv[tot]=P(fac[tot],mod-);

    inv[]=; //求阶乘逆元

    for(int i=tot-;i>=;i--)

        inv[i]=inv[i+]*(i+)%mod;

}

ll Lagrange(ll n,ll k)

{

    rep(i,,k+) f[i]=(f[i-]+P(i,k-))%mod;

    if(n<=k+) return f[n];

    int tot=k+; init(tot);

    ll ans=,now=;

    for(int i=;i<=tot;i++) now=now*(n-i)%mod;

    for(int i=;i<=tot;i++) {

        ll inv1=P(n-i,mod-);

        ll inv2=inv[i-]*inv[tot-i]%mod;

        if((tot-i)&) 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 ;

    return P(x,k+)-Lagrange(x-,k+);

}

int main()

{

    int N;

    while(~scanf("%d",&N)){

        rep(i,,N) scanf("%d",&a[i]);

        sort(a+,a+N+); ans=; sum[]=;

        rep(i,,N) sum[i]=1LL*sum[i-]*a[i]%Mod;

        rep(i,,N) {

            if(a[i]==a[i-]) continue;

            int res=(solve(a[i],N-i+)-solve(a[i-],N-i+)+Mod)%Mod;

            (ans+=1LL*sum[i-]*res%Mod)%=Mod;

        }

        printf("%d\n",ans);

    }

    return ;

}

巴特西

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

最新文章

热门文章