#677326 (C#(csc)) No.1596 Distance Sum in 2D Plane

• 問題: No.1596 Distance Sum in 2D Plane
• ユーザー: さかぽん
• 提出日時: 2021-07-10 22:57:02
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 572 ms / 2,000 ms
• コード長: 1,942 bytes
• コンパイル時間: 3,457 ms
• コンパイル使用メモリ: 112,752 KB
• 実行使用メモリ: 38,148 KB
• 最終ジャッジ日時: 2024-07-02 02:54:09
• 合計ジャッジ時間: 12,164 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	269 ms; 29,380 KB
testcase_01	AC	272 ms; 29,256 KB
testcase_02	AC	566 ms; 38,012 KB
testcase_03	AC	557 ms; 37,816 KB
testcase_04	AC	554 ms; 38,036 KB
testcase_05	AC	562 ms; 38,148 KB
testcase_06	AC	572 ms; 34,076 KB
testcase_07	AC	567 ms; 29,696 KB
testcase_08	AC	555 ms; 29,696 KB
testcase_09	AC	562 ms; 29,696 KB
testcase_10	AC	555 ms; 29,952 KB
testcase_11	AC	531 ms; 29,824 KB
testcase_12	AC	533 ms; 29,824 KB
testcase_13	AC	533 ms; 29,824 KB
testcase_14	AC	27 ms; 17,792 KB
testcase_15	AC	27 ms; 17,664 KB
testcase_16	AC	27 ms; 17,536 KB
testcase_17	AC	28 ms; 17,920 KB
testcase_18	AC	26 ms; 17,664 KB
testcase_19	AC	27 ms; 17,792 KB

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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

class F
{
	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 n2 = 2 * n;
		var mc = new MCombination(n2);
		var r = n2 * mc.MNcr(n2, n) % M;

		foreach (var (t, x, y) in ps)
		{
			if (t == 1)
			{
				r -= mc.MNcr(x + y, x) * mc.MNcr(n2 - x - y - 1, n - y) % M;
			}
			else
			{
				r -= mc.MNcr(x + y, x) * mc.MNcr(n2 - x - y - 1, n - x) % M;
			}
		}

		return MInt(r);
	}

	const long M = 1000000007;
	static long MInt(long x) => (x %= M) < 0 ? x + M : x;
}

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;
}