結果

問題 No.1596 Distance Sum in 2D Plane
コンテスト
ユーザー aogera
提出日時 2025-12-28 17:08:49
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 315 ms / 2,000 ms
コード長 629 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,691 ms
コンパイル使用メモリ 347,480 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-28 17:08:59
合計ジャッジ時間 9,721 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/extc++.h>
using namespace std;
using ll=long long;
#include<atcoder/modint>
using mint=atcoder::modint1000000007;
const int MX=410009;
mint fact[MX],ifact[MX];
mint comb(int n,int k){
	if(fact[0]==0){
		fact[0]=1;
		for(int i=1;i<MX;i++) fact[i]=fact[i-1]*i;
		ifact[MX-1]=fact[MX-1].inv();
		for(int i=MX-1;i>0;i--)ifact[i-1]=ifact[i]*i;
	}
	return fact[n]/fact[k]/fact[n-k];
}
int main(){
	ll N,M;
	cin>>N>>M;
	mint ans=comb(N+N,N)*(N+N);
	while(M--){
		int t,x,y;cin>>t>>x>>y;
		if(t==1) ans-=comb(x+y,x)*comb((N-x-1)+(N-y),N-y);
		if(t==2) ans-=comb(x+y,x)*comb((N-x)+(N-y-1),N-x);
	}
	cout<<ans.val()<<endl;

}
0