AoCoder1983[AGC001E]BBQHard（组合数+dp）

problem

洛谷链接

solution

∑i=1n∑j=i+1n(ai+bi+aj+bjai+aj)=∑i=1n∑j=1n(ai+bi+aj+bjai+aj)−∑i=1n(2(ai+bi)2ai)2\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}=\frac{\sum_{i=1}^{n}\sum_{j=1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}-\sum_{i=1}^{n}\binom{2(a_i+b_i)}{2a_i}}{2} i=1∑n​j=i+1∑n​(ai​+aj​ai​+bi​+aj​+bj​​)=2∑i=1n​∑j=1n​(ai​+aj​ai​+bi​+aj​+bj​​)−∑i=1n​(2ai​2(ai​+bi​)​)​

Cx+yxC_{x+y}^xCx+yx​ 可以视为网格图中 $(0,0)\to (x,y)$ 的路径方案数。

则 Cai+bi+aj+bjai+aj=C(ai+bi)−(−aj,−bj)ai−(−aj)C_{a_i+b_i+a_j+b_j}^{a_i+a_j}=C_{(a_i+b_i)-(-a_j,-b_j)}^{a_i-(-a_j)}Cai​+bi​+aj​+bj​ai​+aj​​=C(ai​+bi​)−(−aj​,−bj​)ai​−(−aj​)​ 即视为 (−aj,−bj)→(ai,bi)(-a_j,-b_j)\rightarrow (a_i,b_i)(−aj​,−bj​)→(ai​,bi​) 的路径方案数。

那么这道题就是多源汇路径数了。

在一开始读入数据的时候，起点方案数增加一，f[−ai][−bi]++f[-a_i][-b_i]++f[−ai​][−bi​]++。

然后暴力转移 $dp$，fi,j←+fi−1,j+fi,j−1f_{i,j}\leftarrow^+ f_{i-1,j}+f_{i,j-1}fi,j​←+fi−1,j​+fi,j−1​，求出到 f[ai][bi]f[a_i][b_i]f[ai​][bi​] 的方案数。

网格图的坐标 $\in [-2000,2000]$，整体平移 $2e3$ ，这都是细节实现。

code

#include
using namespace std;
#define int long long
#define mod 1000000007
#define MAX 2000
int a[200005], b[200005];
int fac[8005], inv[8005];
int f[4005][4005];
int n;int qkpow( int x, int y ) {int ans = 1;while( y ) {if( y & 1 ) ans = ans * x % mod;x = x * x % mod;y >>= 1;}return ans;
}int C( int n, int m ) { if( n < m ) return 0;else return fac[n] * inv[m] % mod * inv[n - m] % mod;
}signed main() {scanf( "%lld", &n );for( int i = 1;i <= n;i ++ ) {scanf( "%lld %lld", &a[i], &b[i] );f[MAX - a[i]][MAX - b[i]] ++;}fac[0] = inv[0] = 1; for( int i = 1;i <= (MAX << 2);i ++ ) fac[i] = fac[i - 1] * i % mod;inv[MAX << 2] = qkpow( fac[MAX << 2], mod - 2 );for( int i = (MAX << 2) - 1;i;i -- ) inv[i] = inv[i + 1] * ( i + 1 ) % mod;for( int i = 0;i <= (MAX << 1);i ++ )for( int j = 0;j <= (MAX << 1);j ++ ) {if( i ) ( f[i][j] += f[i - 1][j] ) %= mod;if( j ) ( f[i][j] += f[i][j - 1] ) %= mod;}int ans = 0, cnt = 0;for( int i = 1;i <= n;i ++ ) {( cnt += C( a[i] + b[i] << 1, a[i] << 1 ) ) %= mod;( ans += f[MAX + a[i]][MAX + b[i]] ) %= mod;}printf( "%lld\n", ( ans - cnt + mod ) % mod * qkpow( 2, mod - 2 ) % mod );return 0;
}