[AGC001E]BBQ Hard

题目

传送门 to AtCoder

思路

显然就是求
∑ i < j ( a i + b i + a j + b j a i + a j ) \sum_{i<j}{a_i+b_i+a_j+b_j\choose a_i+a_j} i<j∑​(ai​+aj​ai​+bi​+aj​+bj​​)

我将问题转化了一下:有多少种方案从原点走到 ( a i + a j , b i + b j ) (a_i+a_j,b_i+b_j) (ai​+aj​,bi​+bj​),也就是两个向量的和?所以我会试图分开计算贡献,也就是类似于先走到 ( a i , b i ) (a_i,b_i) (ai​,bi​) 再走到 ( a j , b j ) (a_j,b_j) (aj​,bj​) 的想法。稍微推了一下,感觉更像是变下指标求和。于是
∑ i < j ( a i + b i + a j + b j a i + a j ) = ∑ i , j ∑ k ( a i + b i k ) ( a j + b j a i + a j − k ) = ∑ i , k ( a i + b i k ) ∑ j ( a j + b j a j + a i − k ) \begin{aligned} &\sum_{i<j}{a_i+b_i+a_j+b_j\choose a_i+a_j}\\ =&\sum_{i,j}\sum_k{a_i+b_i\choose k}{a_j+b_j\choose a_i+a_j-k}\\ =&\sum_{i,k}{a_i+b_i\choose k}\sum_{j}{a_j+b_j\choose a_j+a_i-k}\\ \end{aligned} ==​i<j∑​(ai​+aj​ai​+bi​+aj​+bj​​)i,j∑​k∑​(kai​+bi​​)(ai​+aj​−kaj​+bj​​)i,k∑​(kai​+bi​​)j∑​(aj​+ai​−kaj​+bj​​)​

这个推导看上去很离谱,但也还有迹可循:相当于特殊的 “单独求贡献” 方法。

后面的求和只与 ( a i − k ) (a_i-k) (ai​−k) 有关,可以枚举之后预处理。前面枚举 i , k i,k i,k 后直接调用,时间复杂度 O ( n a ) \mathcal O(na) O(na) 。需要卡常,比如减少乘法的次数(多个数的 ( a i − k ) (a_i-k) (ai​−k) 相同时,左边组合数先求和,再做乘法,可以显著提高效率)。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MOD = 1e9+7;
inline int modAdd(int x,const int y){
	return ((x += y) >= MOD) ? (x-MOD) : x;
}

const int MAXA = 2000, MAXN = 200005;
int c[MAXA<<2|1][MAXA<<2|1], val[MAXA<<1|1];
int a[MAXN], b[MAXN], coe[MAXA<<1|1];
int main(){
	int n = readint(), ans = 0;
	rep(i,0,MAXA<<2) rep(j,c[i][0]=1,i)
		c[i][j] = modAdd(c[i-1][j-1],c[i-1][j]);
	rep(i,1,n) a[i] = readint(), b[i] = readint();
	rep(j,1,n) rep(i,-a[j],MAXA) val[i+MAXA] =
		modAdd(val[i+MAXA],c[a[j]+b[j]][a[j]+i]);
	for(int i=1; i<=n; ++i){
		const int *shit = c[a[i]+b[i]]+(a[i]+b[i])+1;
		for(int *v=coe-b[i]+MAXA,*jb=c[a[i]+b[i]]; jb!=shit;
			++v,++jb) *v = modAdd(*v,*jb); // coefficient
	}
	rep(i,0,MAXA<<1) ans = int((ans+llong(val[i])*coe[i])%MOD);
	rep(i,1,n){ // except i = j
		ans -= c[(a[i]+b[i])<<1][a[i]<<1];
		if(ans < 0) ans += MOD; // keep positive
	}
	ans = int((llong(MOD+1)>>1)*ans%MOD);
	printf("%d\n",ans);
	return 0;
}

正解

上面的那个向量相加,太糟糕了。事实上,它还等价于 ( − a i , − b i ) (-a_i,-b_i) (−ai​,−bi​) 走到 ( a j , b j ) (a_j,b_j) (aj​,bj​) 的方案数!

这两个方案的区别是什么呢?我是让起点都落在原点上,也就是较少的起点;而这个做法是固定起点,虽然有较多的起点。要知道, d p \tt dp dp 喜欢固定而不是少。多与少,只是 d p \tt dp dp 值的关系;而不固定,则是 d p \tt dp dp 状态的事儿。我们要让信息熵足够小。

于是就是一个类似多源点路径方案的东西。在 O ( a 2 ) \mathcal O(a^2) O(a2) 范围内暴力递推即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MOD = 1e9+7;
inline int modAdd(int x,const int y){
	return ((x += y) >= MOD) ? (x-MOD) : x;
}

const int MAXA = 2000;
int jc[MAXA<<2|1], inv[MAXA<<2|1];
void prepare(int n = MAXA<<2){
	rep(i,(jc[0]=inv[0]=jc[1]=inv[1]=1)+1,n){
		jc[i] = int(llong(jc[i-1])*i%MOD);
		inv[i] = int(llong(MOD-MOD/i)*inv[MOD%i]%MOD);
	}
	rep(i,2,n) inv[i] = int(llong(inv[i-1])*inv[i]%MOD);
}
int getC(int n,int m){
	return int(llong(jc[n])*inv[m]%MOD*inv[n-m]%MOD);
}

const int MAXN = 200005;
int x[MAXN], y[MAXN], dp[MAXA<<1|1][MAXA<<1|1];
int main(){
	prepare();
	int n = readint(), ans = 0;
	rep(i,1,n){
		x[i] = readint(), y[i] = readint();
		++ dp[MAXA-x[i]][MAXA-y[i]];
		ans = modAdd(ans,MOD-getC((x[i]+y[i])<<1,x[i]<<1));
	}
	rep(i,0,MAXA<<1) rep(j,0,MAXA<<1){
		if(i) dp[i][j] = modAdd(dp[i][j],dp[i-1][j]);
		if(j) dp[i][j] = modAdd(dp[i][j],dp[i][j-1]);
	}
	rep(i,1,n) ans = modAdd(ans,dp[x[i]+MAXA][y[i]+MAXA]);
	printf("%lld\n",(llong(MOD+1)>>1)*ans%MOD);
	return 0;
}
上一篇:转义符


下一篇:SQL Server discarding SPACE during GROUP BY