用户工具

站点工具


2020-2021:teams:wangzai_milk:atcoder_beginner_contest_127_vp

这是本文档旧的修订版!


比赛链接:AtCoder Beginner Contest 127

E - Cell Distance

题意

给一个 $n\times m$ 的网格和一个整数 $k$ ,每次取 $k$ 个格子 $(x_i,y_i)$ 得到 $v = \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_i-x_j|+|y_i-y_j|)$。求所有不同取法的 $\sum v$ 。

数据范围

$2 \le n\times m \le 2e5$

$2 \le k \le n\times m$

题解

考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){nm-2 \choose k-2}$,所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。

code

code

#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e5+5;
const ll M = 1e9+7;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; }
ll fac[maxn],inv[maxn];
 
void init()
{
    int n = 2e5;
    fac[0] = 1;
    rep(i,1,n) fac[i] = fac[i-1]*i%M;
    inv[n] = qpow(fac[n],M-2);
    per(i,n-1,0) inv[i] = inv[i+1]*(i+1)%M;
}
ll C(ll a,ll b) {return fac[a]*inv[a-b]%M*inv[b]%M;}
int main()
{
    fastio(); init();
    int n,m,k;
    cin>>n>>m>>k;
    ll b = C(n*m-2,k-2);
    ll s = 0,inv2 = qpow(2,M-2);
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            ll a = n * ((j*(j-1)/2 + (1+m-j)*(m-j)/2) % M) % M;
            ll b = m * ((i*(i-1)/2 + (1+n-i)*(n-i)/2) % M) % M;
            s = (s + a + b) % M;
        }
    }
    cout<<b*s%M*inv2%M<<endl;
    return 0;
}
</hidden> 
2020-2021/teams/wangzai_milk/atcoder_beginner_contest_127_vp.1595300397.txt.gz · 最后更改: 2020/07/21 10:59 由 wzx27