2019 Multi-University Training Contest 2

 

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=3030;
ll a[N],pre[N],ans[N],inv3;
const ll mod=998244353;

ll quick(ll a,ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b = b >> 1;
    }
    return res;
}

ll inv(int x){
    return quick(x,mod-2);
}

void init() {
    for (int i = 1; i <= 3000; i++) {
        a[i] = i * (i - 1);
    }
    for (int i = 1; i <= 3000; i++) {
        pre[i] = (pre[i - 1] + a[i]) % mod;
    }

    for (int i = 1; i <= 3000; i++) {
        ans[i] = (pre[i] * inv3%mod *inv(i)) % mod;
    }
}
int main() {
    inv3 = inv(3);
    init();
    int n;
    while (~scanf("%d", &n)) {
        printf("%lld\n", ans[n]);
    }
}

 

 

 

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod=1e6+3;
ll ans[mod+1],n;
int main(){
    ans[0]=1;
    for (int i=1;i<=mod;i++){
        ans[i]=ans[i-1]*i%mod;
    }
    while (~scanf("%lld",&n)){
        if (n>=mod){
            printf("0\n");
        }else{
            printf("%lld\n",ans[n]);
        }
    }
}

 

 

 

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=4e5+5;
int a[maxn],n,rt[maxn],q;
vector<int>vec;
struct pstree{
    struct pst{
        int lch,rch,val;
    }z[maxn*20];
    int cnt;
    inline void insert(int &p,int pre,int l,int r,int q) {
        p = ++cnt;
        z[p] = z[pre];
        ++z[p].val;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if (q <= mid) {
            insert(z[p].lch, z[pre].lch, l, mid, q);
        } else {
            insert(z[p].rch, z[pre].rch, mid + 1, r, q);
        }
    }

    inline int query(int l1,int r1,int l,int r,int q) {
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        int tmp = z[z[r1].lch].val - z[z[l1].lch].val;
        if (tmp >= q) {
            return query(z[l1].lch, z[r1].lch, l, mid, q);
        } else {
            return query(z[l1].rch, z[r1].rch, mid + 1, r, q - tmp);
        }
    }
}pstree;
int main() {
    while (~scanf("%d%d", &n, &q)) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            vec.push_back(a[i]);
        }
        sort(vec.begin(), vec.end());
        vec.erase(unique(vec.begin(), vec.end()), vec.end());
        for (int i = 1; i <= n; i++) {
            a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1;
            pstree.insert(rt[i], rt[i - 1], 1, n, a[i]);
        }
        while (q--) {
            int l,r;
            scanf("%d%d", &l, &r);
            int cnt = r - l + 1;
            int f = 0;
            if (cnt < 3) {
                puts("-1");
                continue;
            }
            int tmp = min(60, cnt);
            int maxx[3];
            for (int i = 0; i < 3; i++) {
                maxx[i] = vec[pstree.query(rt[l - 1], rt[r], 1, n, cnt - i) - 1];
            }
            if (maxx[0] - maxx[1] < maxx[2]) {
                printf("%lld\n", (ll) maxx[0] + maxx[1] + maxx[2]);
                continue;
            }
            for (int i = 3; i < tmp; i++) {
                maxx[0] = maxx[1];
                maxx[1] = maxx[2];
                maxx[2] = vec[pstree.query(rt[l - 1], rt[r], 1, n, cnt - i) - 1];
                if (maxx[0] - maxx[1] < maxx[2]) {
                    f = 1;
                    printf("%lld\n", (ll) maxx[0] + maxx[1] + maxx[2]);
                    break;
                }
            }
            if (!f) {
                puts("-1");
            }
        }
        vec.clear();
        pstree.cnt = 0;
    }
}