結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:13:40 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 861 ms / 2,000 ms |
コード長 | 715 bytes |
コンパイル時間 | 1,485 ms |
コンパイル使用メモリ | 168,448 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-01 16:47:10 |
合計ジャッジ時間 | 12,828 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,MOD=1e9+7,a,b,ans,bik[400001],c; ll f(ll x,ll y){ if(y==0)return 1; if(y%2==0)return f(x,y/2)*f(x,y/2)%MOD; return x*f(x,y-1)%MOD; } ll comb(ll x, ll y){ return bik[x]*f(bik[x-y],MOD-2)%MOD*f(bik[y],MOD-2)%MOD; } int main(void){ cin>>n>>m; bik[0]=1; for(ll i=1;i<=400000;i++){ bik[i]=bik[i-1]*i; bik[i]%=MOD; } //cout<<comb(n+m,m)<<endl; ans=comb(2*n,n)*2*n%MOD; for(int i=0;i<m;i++){ cin>>a>>b>>c; if(a==1)ans-=comb(b+c,c)*comb(2*n-b-c-1,n-c)%MOD; if(a==2)ans-=comb(b+c,c)*comb(2*n-b-c-1,n-b)%MOD; ans%=MOD; } cout<<(ans+MOD)%MOD<<endl; }