[AGC001E]BBQ Hard

BBQ Hard

题解

首先,我们可以考虑组合数是可以被表示成路径的形式的, ( n + m m ) \binom{n+m}{m} (mn+m​)可以表示从点 ( 0 , 0 ) (0,0) (0,0)到点 ( n , m ) (n,m) (n,m)的简单路径(向上走或向右走)数。
那么显然,我们 ( a i + a j + b i + b j a i + a j ) \binom{a_i+a_j+b_i+b_j}{a_i+a_j} (ai​+aj​ai​+aj​+bi​+bj​​)可以表示从点 ( 0 , 0 ) (0,0) (0,0)到点 ( a i + a j , b i + b j ) (a_i+a_j,b_i+b_j) (ai​+aj​,bi​+bj​)的简单路径数量。但显然

我们不可能对于每个 ( a i + a j , b i + b j ) (a_i+a_j,b_i+b_j) (ai​+aj​,bi​+bj​)都求一条路径,但不妨再观察一下, ( 0 , 0 ) (0,0) (0,0)到 ( 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​)的路径数的。
我们可以用 d p dp dp求出所有的 ( − a i , − b i ) (-a_i,-b_i) (−ai​,−bi​)到所有的 ( a j , b j ) (a_j,b_j) (aj​,bj​)的路径数。
记 d p x , y dp_{x,y} dpx,y​为所有的 ( − a i , − b i ) (-a_i,-b_i) (−ai​,−bi​)到点 ( x , y ) (x,y) (x,y)的简单路径数, ∑ j = 1 n d p a i , b i \sum_{j=1}^{n}dp_{a_i,b_i} ∑j=1n​dpai​,bi​​就是答案。

时间复杂度 O ( n + A B ) O\left(n+AB\right) O(n+AB)。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define MAXM 4005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int mod=1e5+3;
const int inv2=5e8+4;
const int jzm=2333;
const int zero=2000;
const int n1=1000;
const int M=100000;
const int orG=3,ivG=332748118;
const long double Pi=acos(-1.0);
const double eps=1e-12;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,a[MAXN],b[MAXN],dp[MAXM][MAXM],ans,fac[MAXM*2],inv[MAXM*2],ff[MAXM*2];
void init(){
	fac[0]=fac[1]=inv[0]=inv[1]=ff[1]=1;
	for(int i=2;i<=8000;i++)
		fac[i]=1ll*i*fac[i-1]%mo,
		ff[i]=1ll*(mo-mo/i)*ff[mo%i]%mo,
		inv[i]=1ll*ff[i]*inv[i-1]%mo;
}
int C(int x,int y){
	if(x<y||x<0||y<0)return 0;
	return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
signed main(){
	read(n);init();
	for(int i=1;i<=n;i++)read(a[i]),read(b[i]),dp[zero-a[i]][zero-b[i]]++;
	for(int i=1;i<=8000;i++)
		for(int x=max(0,i-4000),y=min(4000,i);x<=4000&&y>=0;x++,y--){
			if(x)Add(dp[x][y],dp[x-1][y],mo);
			if(y)Add(dp[x][y],dp[x][y-1],mo);
		}
	for(int i=1;i<=n;i++)
		Add(ans,dp[zero+a[i]][zero+b[i]],mo),
		Add(ans,mo-C(2*(a[i]+b[i]),2*a[i]),mo);
	printf("%d\n",1ll*inv2*ans%mo);
	return 0;
}

谢谢!!!

上一篇:题解-AGC046F Forbidden Tournament/CF1338E JYPnation (hard)


下一篇:astronaut, astronomy