Editorial for Bedao OI Contest 5 - Sắp xếp chữ cái
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.
#include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(i,l,r) for(auto i = l; i <= r; i++) #define FORD(i,r,l) for(auto i = r; i >= l; i--) #define MOD 1000000007 #define N 200005 int n; int a[N], b[N]; ll dp[4005][4005]; ll f[N], finv[N]; ll pw(ll a, int b){ ll Ans = 1; int LOG = 31 - __builtin_clz(b); FOR(i, 0, LOG){ if(b>>i&1) Ans = Ans * a % MOD; a = a * a % MOD; } return Ans; } ll C(int k, int n){ return f[n] * finv[k] % MOD * finv[n-k] % MOD; } inline void add(ll &a, ll b){ a += b; if(a >= MOD) a -= MOD; if(a < 0) a += MOD; } inline void Solve(){ cin >> n; FOR(i, 1, n){ cin >> a[i] >> b[i]; dp[2000 + a[i]][2000 + b[i]]++; } f[0] = 1; int m = 10000; FOR(i, 1, m) f[i] = f[i-1] * i % MOD; finv[m] = pw(f[m], MOD-2); FORD(i, m-1, 0) finv[i] = finv[i+1] * (i+1) % MOD; FORD(i, 4000, 0) FORD(j, 4000, 0){ add(dp[i][j], (dp[i+1][j] + dp[i][j+1]) % MOD); } ll Ans = 0; FOR(i, 1, n){ ll cur = dp[2000 - a[i]][2000 - b[i]]; add(cur, -C(a[i] + a[i], a[i] + a[i] + b[i] + b[i])); add(Ans, cur); } cout << (Ans * pw(2, MOD-2)) % MOD; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define NAME "ORDLETTER" if(fopen(NAME".inp", "r")){ freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout); } Solve(); return 0; }
Comments