結果
問題 | No.1596 Distance Sum in 2D Plane |
ユーザー |
![]() |
提出日時 | 2021-07-09 22:03:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 2,501 bytes |
コンパイル時間 | 923 ms |
コンパイル使用メモリ | 94,292 KB |
実行使用メモリ | 9,776 KB |
最終ジャッジ日時 | 2024-07-01 16:29:03 |
合計ジャッジ時間 | 4,100 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <iostream>#include <string>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <list>#include <iterator>#include <cassert>#include <numeric>#include <functional>#include <ctime>#include <bitset>#pragma warning(disable:4996)//#define ATCODER#ifdef ATCODER#include <atcoder/all>#endiftypedef long long ll;typedef unsigned long long ull;#define LINF 9223300000000000000#define LINF2 1223300000000000000#define LINF3 1000000000000#define INF 2140000000const long long MOD = 1000000007;//const long long MOD = 998244353;using namespace std;#ifdef ATCODERusing namespace atcoder;#endifconst int max_comb = 410000;vector<ll> fac(max_comb + 1); //n! (mod M)vector<ll> ifac(max_comb + 1); //k!^(-1) (mod M)ll mpow(ll x, ll n) { //x^n(mod M)ll ans = 1;while (n != 0) {if (n & 1) ans = ans * x % MOD;x = x * x % MOD;n = n >> 1;}return ans;}ll minv(ll x) {return mpow(x, MOD - 2);}ll comb(int a, int b) { // C(a,b) = a! * b!^(-1) * (a-b)^(-1)if (a == 0 && b == 0)return 1;if (a < b || a < 0)return 0;ll tmp = ifac[a - b] * ifac[b] % MOD;return tmp * fac[a] % MOD;}ll perm(int a, int b) { // P(a,b) = a! * (a-b)!^(-1)if (b == 0)return 1;if (a < b || a < 0)return 0;ll tmp = ifac[a - b] % MOD;return tmp * fac[a] % MOD;}void pre_comb(){fac[0] = 1;ifac[0] = 1;for (int i = 0; i < max_comb; i++) {fac[i + 1] = fac[i] * (i + 1) % MOD; // n!(mod M)ifac[i + 1] = ifac[i] * minv(i + 1) % MOD; // k!^(-1) (mod M)}return;}void solve(){pre_comb();int n, m;scanf("%d%d", &n, &m);ll ans0 = 0;for (int i = 0; i < m; i++) {int t, x, y;scanf("%d%d%d", &t, &x, &y);if (t == 1) {ll tmp = comb(x + y, x)*comb(n - x - 1 + n - y, n - x - 1)%MOD;ans0 = (ans0 + tmp) % MOD;}else {ll tmp = comb(x + y, x)*comb(n - x - 1 + n - y, n - x) % MOD;ans0 = (ans0 + tmp) % MOD;}}ll ans = comb(n * 2, n)*n * 2 % MOD;ans = (ans - ans0 + MOD) % MOD;printf("%lld\n", ans);return;}int main(){#if 1solve();#elseint T, t;scanf("%d", &T);for (t = 0; t < T; t++) {//printf("Case #%d: ", t + 1);solve();}#endifreturn 0;}