結果

問題 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;
}
0