yukicoder : No.1596 Distance Sum in 2D Plane

どんどん行きます。
https://yukicoder.me/problems/no/1596

問題

2次元座標上(0,0)から(N,N)に移動することを考える。
通常、コストを1掛け、X座標かY座標を1増やせる。

ただし、Mか所だけ、ノーコストで移動できる場所・向きが指定される。
(0,0)から(N,N)に至る全経路における総コストを求めよ。

解法

ノーコストのMか所を無視すると、コストは2N、移動経路はC(2N,N)通りである。
ここから、ノーコストで移動できるケースの分を差し引こう。

例えば、(x,y)→(x+1,y)がノーコストで移動できる場合、この移動経路を通るC(x+y,x)*C(2N-(x+1+y),N-y)だけ引けばよい。

ll mo=1000000007;
ll comb(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;
}

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll ret=comb(N+N,N)*2*N%mo;
	FOR(i,M) {
		cin>>j>>x>>y;
		if(j==1) ret+=mo-comb(x+y,x)*comb(2*N-(x+1+y),N-y)%mo;
		if(j==2) ret+=mo-comb(x+y,x)*comb(2*N-(x+y+1),N-x)%mo;
		
	}
	cout<<ret%mo<<endl;
}

まとめ

実装が軽くて楽。