AtCoder AGC #001 : E - BBQ Hard

うーむ、このテクは知らなかった。
http://agc001.contest.atcoder.jp/tasks/agc001_e

問題

N種類の素材がある。各素材は肉がA[i]個、野菜がB[i]個からなる。
うち２つの素材を選んだ上で、串に肉(A[i]+A[j])個、野菜(B[i]+B[j])個を順に刺す順番の総和を求めよ。

解法

求めたいのは、である。

A[i],B[i]の絶対値が割と小さいことを利用しよう。
２次元座標上で格子点(-A[i],-B[i])から(A[j],B[j])に、上及び右の格子点を辿っていく方法を数え上げるとに相当する。

そこで、各(-A[i],-B[i])から初めて各(A[j],B[j])に到達する手法をDPでまとめて数え上げよう。
この値は(-A[i],-B[i])から(A[i],B[i])へ移動するケースを含んでいたり、i＞jに対し(-A[i],-B[i])から(A[j],B[j])へ移動するケースも含んでしまっている。
よってDPの数え上げ結果からを引いたうえで２で割ればよい。

int N;
int A[202000], B[202000];
ll dp[4040][4040];
ll yes[4040][4040];
ll mo=1000000007;
ll ret=0;

ll combi(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:combi(P_+Q_-1,Q_);}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i]>>B[i];
		dp[2010-A[i]][2010-B[i]]++;
		yes[2010+A[i]][2010+B[i]]++;
	}
	FOR(x,4020) FOR(y,4020) {
		if(yes[x][y]) (ret += yes[x][y]*dp[x][y])%=mo;
		dp[x+1][y] += dp[x][y];
		if(dp[x+1][y]>=mo) dp[x+1][y]-=mo;
		dp[x][y+1] += dp[x][y];
		if(dp[x][y+1]>=mo) dp[x][y+1]-=mo;
	}
	
	FOR(i,N) {
		ret -= combi(2*(A[i]+B[i]),2*A[i]);
		if(ret<0) ret+=mo;
	}
	cout<<ret*((mo+1)/2)%mo<<endl;
	
}

まとめ

まぁDで詰まったから本番問題もろくに見てないんだけどね。