AtCoder AGC001E BBQ Hard (DP、组合计数)

题目链接: https://atcoder.jp/contests/agc001/tasks/agc001_e

题解:

求\(\sum^n_{i=1}\sum^n_{j=i+1} {A_i+A_j+B_i+B_j\choose A_i+A_j}\)

虽然\(n\)很大，但是\(A_i,B_i\le 2000\), 所以我们可以考虑一个权值平方的做法

观察到那个式子就等于从\((-A_j,-B_j)\)走到\((A_i,B_i)\)的NE Lattice Path条数，那么就相当于从\(S\)连边向每个\((-A_i,B_i)\), 从每个\((A_i,B_i)\)连边向\(T\), 然后求\(S\)到\(T\)的路径条数，减去\(i\)和\(j\)相等的情况再除以\(2\)就是答案。

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#define llong long long

using namespace std;

const int N = 2e5;

const int C = 2000;

const int P = 1e9+7;

llong a[N+3],b[N+3];

llong fact[N+3],finv[N+3];

llong dp[C+C+7][C+C+7];

int n;

llong quickpow(llong x,llong y)

{

	llong cur = x,ret = 1ll;

	for(int i=0; y; i++)

	{

		if(y&(1ll<<i)) {ret = ret*cur%P; y-=(1ll<<i);}

		cur = cur*cur%P;

	}

	return ret;

}

llong comb(llong x,llong y) {return x<0 || y<0 || x<y ? 0ll : fact[x]*finv[x-y]%P*finv[y]%P;}

int main()

{

	fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;

	finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=0; i--) finv[i] = finv[i+1]*(i+1)%P;

	scanf("%d",&n);

	for(int i=1; i<=n; i++) scanf("%d%d",&a[i],&b[i]);

	for(int i=1; i<=n; i++) dp[C-a[i]][C-b[i]] += 1ll;

	for(int i=1; i<=C+C; i++) dp[0][i] += dp[0][i-1];

	for(int i=1; i<=C+C; i++) dp[i][0] += dp[i-1][0];

	for(int i=1; i<=C+C; i++)

	{

		for(int j=1; j<=C+C; j++)

		{

			dp[i][j] = dp[i][j]+dp[i-1][j]+dp[i][j-1];

			dp[i][j] %= P;

		}

	}

	llong ans = 0ll;

	for(int i=1; i<=n; i++) ans = (ans+dp[C+a[i]][C+b[i]])%P;

	for(int i=1; i<=n; i++) ans = (ans-comb(a[i]+a[i]+b[i]+b[i],a[i]+a[i])+P)%P;

	ans = ans*(P+1)/2%P;

	printf("%lld\n",ans);

	return 0;

}

AtCoder AGC001E BBQ Hard (DP、组合计数)的相关教程结束。