結果

問題 No.8048 Order and Harmony
ユーザー ats5515
提出日時 2019-04-01 22:59:34
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 458 ms / 2,000 ms
コード長 3,319 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 83,596 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-27 03:59:49
合計ジャッジ時間 11,835 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0