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.
#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

Please read the guidelines before commenting.


There are no comments at the moment.