Submission #530343

#	Time	Username	Problem	Language	Result	Execution time	Memory
530343		i_am_noob	W (RMI18_w)	C++17	100 / 100	94 ms	23572 KiB

w

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif

const int mod=1000000007;
const int maxn=300005,maxm=5,maxk=7777714;

//i_am_noob
int n,cnt[maxn],val[maxn][5];

int add(int x, int y){x+=y; if(x>=mod) x-=mod; return x;}
int sub(int x, int y){x-=y; if(x<0) x+=mod; return x;}
int Pow(int a, int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}

int solve1(int t){
    int res=0;
    int pre[maxn],suf[maxn];
    pre[0]=pre[1]=1;
    rep2(i,1,n) pre[i+1]=pre[i]*val[cnt[i]][2+t]%mod;
    suf[0]=1;
    rep2(i,1,n+1) suf[i]=suf[i-1]*val[cnt[n-i]][t]%mod;
    rep2(i,1,n) if(cnt[i]){
        res+=pre[i]*suf[n-1-i]%mod*val[cnt[i]-1][1+t]%mod;
    }
    res%=mod;
    return res;
}

int solve2(int t1, int t2){
    int pre[maxn],suf[maxn];
    pre[0]=pre[1]=1;
    rep2(i,1,n) pre[i+1]=pre[i]*val[cnt[i]][1+t1]%mod;
    suf[0]=1;
    rep2(i,1,n+1) suf[i]=suf[i-1]*val[cnt[n-i]][t1+t2]%mod;
    int res=0,cur=0;
    rep2(i,2,n) if(cnt[i]){
        cur=cur*val[cnt[i-1]][2+t1+t2]%mod;
        cur=add(cur,pre[i-1]*val[cnt[i-1]-1][2+t1]%mod);
        res+=cur*val[cnt[i]-1][1+t1+t2]%mod*suf[n-1-i]%mod;
    }
    res%=mod;
    return res;
}

void orzck(){
    rep(maxn) val[i][0]=0,val[i][1]=1;
    val[0][0]=1;
    rep2(j,2,5) rep(maxn){
        if(i==0) val[i][j]=1;
        else val[i][j]=add(val[i-1][j],val[i][j-1]);
    }
    cin >> n;
    vector<int> vec;
    rep(n){
        int x;
        cin >> x;
        vec.pb(x);
    }
    sort(all(vec));
    int cur=0;
    rep(n){
        if(i&&vec[i]>vec[i-1]) cur++;
        cnt[cur]++;
    }
    int res=(solve1(2)-2*solve1(1)+solve1(0))*(cnt[0]-1)+(solve2(1,1)-solve2(0,1)-solve2(1,0)+solve2(0,0))*2;
    res%=mod; res+=mod; res%=mod;
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    orzck();
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50