結果

問題 No.1596 Distance Sum in 2D Plane
コンテスト
ユーザー totori_nyaa
提出日時 2021-07-09 21:47:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 3,501 bytes
コンパイル時間 1,847 ms
コンパイル使用メモリ 172,784 KB
実行使用メモリ 63,288 KB
最終ジャッジ日時 2024-07-01 15:50:25
合計ジャッジ時間 5,500 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
long double eps = 1e-9;
long double pi = acos(-1);


template< int mod = 1000000007 >
struct ModInt {
	int x;
	ModInt() : x(0) {}
	ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
	ModInt &operator+=(const ModInt &p) {
		if((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator-=(const ModInt &p) {
		if((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator*=(const ModInt &p) {
		x = (int) (1LL * x * p.x % mod);
		return *this;
	}
	ModInt &operator/=(const ModInt &p) {
		*this *= p.inverse();
		return *this;
	}

	ModInt operator-() const { return ModInt(-x); }
	ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
	ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
	ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
	ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
	bool operator==(const ModInt &p) const { return x == p.x; }
	bool operator!=(const ModInt &p) const { return x != p.x; }

	ModInt inverse() const {
		int a = x, b = mod, u = 1, v = 0, t;
		while(b > 0) {
			t = a / b;
			swap(a -= t * b, b);
			swap(u -= t * v, v);
		}
		return ModInt(u);
	}

	ModInt pow(int64_t n) const {
		ModInt ret(1), mul(x);
		while(n > 0) {
			if(n & 1) ret *= mul;
			mul *= mul;
			n >>= 1;
		}
		return ret;
	}

	friend ostream &operator<<(ostream &os, const ModInt &p) {
		return os << p.x;
	}

	friend istream &operator>>(istream &is, ModInt &a) {
		int64_t t;
		is >> t;
		a = ModInt< mod >(t);
		return (is);
	}

	static int get_mod() { return mod; }
};

const int mod = 1000000007;
// const int mod = 998244353;
using mint = ModInt< mod >;
const int MAX = 5100005;

mint fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++){
		fac[i] = fac[i - 1] * i;
	}
	finv[MAX-1] = fac[MAX-1].inverse();
	for(int i=MAX-2;i>=1;i--){
		finv[i] = finv[i+1]*(i+1);
		inv[i+1] = fac[i]*finv[i+1];
	}
}

// 二項係数計算
mint COM(int n, int k){
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k]);
}

// n次多項式f(x)に対して、f(0),f(1),...f(n)が分かっているなら任意のtに対してf(t)が復元できる
// return f(t)
mint LagrangePolynomial(vector<mint> y,ll T){
	int n=y.size()-1;
	if (T<=n) return y[T];
	vector<mint> dp(n+1,1),pd(n+1,1),fac(n+1,1),finv(n+1,1);
	for (int i=0;i<n;++i) dp[i+1]=dp[i]*(T-i);
	for (int i=n;i>0;--i) pd[i-1]=pd[i]*(T-i);
	for (int i=1;i<n+1;++i) fac[i]=fac[i-1]*i;
	finv[n]=mint(1)/fac[n];
	for (int i=n;i>0;--i) finv[i-1]=finv[i]*i;
	mint res=0;
	for (int i=0;i<=n;++i){
		mint x=y[i]*dp[i]*pd[i]*finv[i]*finv[n-i];
		if ((n-i)&1) res-=x;
		else res+=x;
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);

	COMinit();
	int n,m;
	cin>>n>>m;
	mint ans = COM(n+n,n) * (n+n);
	for(int i=0;i<m;i++){
		int t,x,y;
		cin>>t>>x>>y;
		if(t == 1){
			ans -= COM(x+y,x) * COM(n+n-x-y-1,n-x-1);
		}
		else{
			ans -= COM(x+y,x)* COM(n+n-x-y-1,n-y-1);
		}
	}
	cout << ans << endl;
}
0