Editorial for Bedao Regular Contest 06 - PMED


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 2e6+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e9+1;
const int SQRT = 44721;

ll add(ll a, ll b) { return (a+b) % MOD; }
ll sub(ll a, ll b) { return (a-b+MOD) % MOD; }
ll mul(ll a, ll b) { return (a*b) % MOD; }

int k, n = 0;
int val[200005], cnt[200005], f[200005];
int fac[MAX], infac[MAX];

int inv(int val) {
    int curr = 1, temp = MOD-2;

    while(temp > 0) {
        if(temp & 1) curr = mul(curr, val);
        val = mul(val, val);
        temp >>= 1;
    }

    return curr;
}

void precompute() {
    fac[0] = 1;
    fo(i, 1, MAX-1) fac[i] = mul(i, fac[i-1]);
    infac[MAX-1] = inv(fac[MAX-1]);
    _fo(i, MAX-2, 0) infac[i] = mul(i+1, infac[i+1]);
}

int comb(int a, int b) {
    return (b > a) ? 0 : mul(mul(fac[a], infac[a-b]), infac[b]);
}

int path(int u, int d) {
    if(u > d) return 0;
    return sub(comb(u+d, u), comb(u+d, u-1));
}

int solve() {
    int temp = 0, res = 0;
    fo(i, 1, k) {
        temp += cnt[i];
        f[i] = mul(mul(fac[temp], fac[n-temp]), path(n-temp, temp));
    }
    fo(i, 1, k) res = add(res, mul(val[i], sub(f[i], f[i-1])));
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    precompute();
    cin >> k;
    fo(i, 1, k) {
        cin >> val[i] >> cnt[i];
        n += cnt[i];
    }  
    cout << solve();
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.