結果

問題 No.1596 Distance Sum in 2D Plane
コンテスト
ユーザー さかぽん
提出日時 2021-07-09 22:40:00
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 2,143 bytes
コンパイル時間 2,368 ms
コンパイル使用メモリ 109,568 KB
実行使用メモリ 144,128 KB
最終ジャッジ日時 2024-07-01 17:24:00
合計ジャッジ時間 9,539 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Linq;

class F
{
	const long M = 1000000007;
	static int[] Read() => Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
	static (int, int) Read2() { var a = Read(); return (a[0], a[1]); }
	static (int t, int x, int y) Read3() { var a = Read(); return (a[0], a[1], a[2]); }
	static long[] ReadL() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
	static void Main() => Console.WriteLine(Solve());
	static object Solve()
	{
		var (n, m) = Read2();
		var ps = Array.ConvertAll(new bool[m], _ => Read3());

		var d = ps.ToDictionary(p => (p.x, p.y), p => p.t);

		var r = 0L;
		var mc = new MCombination(2 * n);

		// t == 1
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j <= n; j++)
			{
				if (d.ContainsKey((i, j)) && d[(i, j)] == 1) continue;

				r += mc.MNcr(i + j, i) * mc.MNcr(2 * n - i - j - 1, n - j);
				r %= M;
			}
		}

		// t == 2
		for (int i = 0; i <= n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (d.ContainsKey((i, j)) && d[(i, j)] == 2) continue;

				r += mc.MNcr(i + j, i) * mc.MNcr(2 * n - i - j - 1, n - i);
				r %= M;
			}
		}

		return r;
	}
}

public class MCombination
{
	//const long M = 998244353;
	const long M = 1000000007;
	static long MPow(long b, long i)
	{
		long r = 1;
		for (; i != 0; b = b * b % M, i >>= 1) if ((i & 1) != 0) r = r * b % M;
		return r;
	}
	static long MInv(long x) => MPow(x, M - 2);

	static long[] MFactorials(int n)
	{
		var f = new long[n + 1];
		f[0] = 1;
		for (int i = 1; i <= n; ++i) f[i] = f[i - 1] * i % M;
		return f;
	}

	// nPr, nCr を O(1) で求めるため、階乗を O(n) で求めておきます。
	long[] f, f_;
	public MCombination(int nMax)
	{
		f = MFactorials(nMax);
		f_ = Array.ConvertAll(f, MInv);
	}

	public long MFactorial(int n) => f[n];
	public long MInvFactorial(int n) => f_[n];
	public long MNpr(int n, int r) => n < r ? 0 : f[n] * f_[n - r] % M;
	public long MNcr(int n, int r) => n < r ? 0 : f[n] * f_[n - r] % M * f_[r] % M;

	// nMax >= 2n としておく必要があります。
	public long MCatalan(int n) => f[2 * n] * f_[n] % M * f_[n + 1] % M;
}
0