結果
問題 | No.3048 Order and Harmony |
ユーザー | ats5515 |
提出日時 | 2019-04-01 22:59:34 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 493 ms / 2,000 ms |
コード長 | 3,319 bytes |
コンパイル時間 | 634 ms |
コンパイル使用メモリ | 76,876 KB |
実行使用メモリ | 4,504 KB |
最終ジャッジ日時 | 2023-08-18 02:05:22 |
合計ジャッジ時間 | 13,408 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,384 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 3 ms
4,380 KB |
testcase_03 | AC | 403 ms
4,384 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 3 ms
4,380 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,380 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 2 ms
4,380 KB |
testcase_17 | AC | 2 ms
4,384 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 3 ms
4,380 KB |
testcase_20 | AC | 3 ms
4,376 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,376 KB |
testcase_24 | AC | 2 ms
4,376 KB |
testcase_25 | AC | 411 ms
4,380 KB |
testcase_26 | AC | 448 ms
4,380 KB |
testcase_27 | AC | 436 ms
4,380 KB |
testcase_28 | AC | 338 ms
4,380 KB |
testcase_29 | AC | 2 ms
4,384 KB |
testcase_30 | AC | 334 ms
4,380 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 402 ms
4,376 KB |
testcase_33 | AC | 2 ms
4,376 KB |
testcase_34 | AC | 364 ms
4,376 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 360 ms
4,380 KB |
testcase_37 | AC | 452 ms
4,376 KB |
testcase_38 | AC | 30 ms
4,504 KB |
testcase_39 | AC | 476 ms
4,380 KB |
testcase_40 | AC | 444 ms
4,376 KB |
testcase_41 | AC | 481 ms
4,380 KB |
testcase_42 | AC | 421 ms
4,380 KB |
testcase_43 | AC | 1 ms
4,376 KB |
testcase_44 | AC | 472 ms
4,380 KB |
testcase_45 | AC | 35 ms
4,380 KB |
testcase_46 | AC | 426 ms
4,376 KB |
testcase_47 | AC | 367 ms
4,376 KB |
testcase_48 | AC | 382 ms
4,376 KB |
testcase_49 | AC | 1 ms
4,380 KB |
testcase_50 | AC | 347 ms
4,376 KB |
testcase_51 | AC | 1 ms
4,376 KB |
testcase_52 | AC | 1 ms
4,380 KB |
testcase_53 | AC | 470 ms
4,380 KB |
testcase_54 | AC | 1 ms
4,380 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 445 ms
4,380 KB |
testcase_57 | AC | 1 ms
4,380 KB |
testcase_58 | AC | 1 ms
4,376 KB |
testcase_59 | AC | 2 ms
4,380 KB |
testcase_60 | AC | 349 ms
4,380 KB |
testcase_61 | AC | 408 ms
4,380 KB |
testcase_62 | AC | 371 ms
4,376 KB |
testcase_63 | AC | 1 ms
4,380 KB |
testcase_64 | AC | 493 ms
4,376 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <string> #include <iomanip> #include <algorithm> #include <cmath> #include <stdio.h> using namespace std; #define int long long int MOD = 1000000007; void extgcd(int a, int b, int& x, int& y) { if (b != 0) { extgcd(b, a%b, y, x); y -= (a / b)*x; } else { x = 1; y = 0; } } int mod_inverse(int a, int m) { int x, y; extgcd(a, m, x, y); return (m + x % m) % m; } int A[101]; int calc(int a, int b) { int B = (int)1e7; int res = 1; int aa = a / B; int bb = b / B; //cerr << aa << " " << bb << endl; if (aa == bb) { for (int i = a; i <= b; i++) { res = (res * i) % MOD; } } else { for (int k = aa + 2; k <= bb; k++) { res = (res * A[k]) % MOD; } for (int i = a; i < B * (aa + 1); i++) { res = (res * i) % MOD; } for (int i = B * bb; i <= b; i++) { res = (res * i) % MOD; } } return res; } signed main() { cin.tie(0); ios::sync_with_stdio(false); { A[1] = 250015370; A[2] = 816360219; A[3] = 632628961; A[4] = 837059421; A[5] = 492113872; A[6] = 838549195; A[7] = 527026130; A[8] = 2725451; A[9] = 592711778; A[10] = 882026183; A[11] = 670893849; A[12] = 351004008; A[13] = 438918594; A[14] = 52456784; A[15] = 684334051; A[16] = 83138789; A[17] = 674644528; A[18] = 327400157; A[19] = 524557866; A[20] = 91684762; A[21] = 606472392; A[22] = 506227303; A[23] = 527865420; A[24] = 272027049; A[25] = 402019651; A[26] = 585089616; A[27] = 571687560; A[28] = 856991697; A[29] = 822078026; A[30] = 480501729; A[31] = 134463883; A[32] = 114108400; A[33] = 282946968; A[34] = 192477408; A[35] = 890608175; A[36] = 449841455; A[37] = 368185111; A[38] = 980303312; A[39] = 145404435; A[40] = 381590563; A[41] = 696644281; A[42] = 262681284; A[43] = 645493869; A[44] = 408310692; A[45] = 603153168; A[46] = 290910897; A[47] = 324797499; A[48] = 790789318; A[49] = 717762590; A[50] = 800901939; A[51] = 341599514; A[52] = 161490215; A[53] = 563667534; A[54] = 582423095; A[55] = 765443890; A[56] = 415275608; A[57] = 174325588; A[58] = 672830327; A[59] = 368035915; A[60] = 818904786; A[61] = 660689448; A[62] = 483231847; A[63] = 179366794; A[64] = 289579701; A[65] = 138353584; A[66] = 920634748; A[67] = 59249820; A[68] = 726328027; A[69] = 885279564; A[70] = 56665999; A[71] = 454487400; A[72] = 554404297; A[73] = 152710801; A[74] = 168284359; A[75] = 892037677; A[76] = 452469553; A[77] = 46232623; A[78] = 631812016; A[79] = 207979793; A[80] = 747147886; A[81] = 678103418; A[82] = 342657232; A[83] = 205346810; A[84] = 700242598; A[85] = 552124079; A[86] = 317400728; A[87] = 149545342; A[88] = 564651632; A[89] = 583968907; A[90] = 24576788; A[91] = 886889465; A[92] = 468969837; A[93] = 940316226; A[94] = 881378614; A[95] = 225022223; A[96] = 629841046; A[97] = 290717452; A[98] = 738407761; A[99] = 227223604; A[100] = 91987333; } int N; cin >> N; if (N % 2 == 1) { cout << 0 << endl; return 0; } int N2 = N; N /= 2; int u = calc(N + 1, N2); int d = calc(1, N); //cerr << u << " " << d << endl; cout << (u * mod_inverse(d, MOD) % MOD) << endl; }