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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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