#346899 (C) No.797 Noelちゃんとピラミッド

提出ソース

結果

問題	No.797 Noelちゃんとピラミッド
ユーザー	asugen0402
提出日時	2019-05-15 13:03:23
言語	C (gcc 12.3.0)
結果	AC
実行時間	41 ms / 2,000 ms
コード長	3,562 bytes
コンパイル時間	380 ms
コンパイル使用メモリ	32,256 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-09-13 21:03:19
合計ジャッジ時間	4,592 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	1 ms 5,376 KB
testcase_03	AC	41 ms 5,376 KB
testcase_04	AC	39 ms 5,376 KB
testcase_05	AC	39 ms 5,376 KB
testcase_06	AC	40 ms 5,376 KB
testcase_07	AC	39 ms 5,376 KB
testcase_08	AC	40 ms 5,376 KB
testcase_09	AC	39 ms 5,376 KB
testcase_10	AC	40 ms 5,376 KB
testcase_11	AC	39 ms 5,376 KB
testcase_12	AC	39 ms 5,376 KB
testcase_13	AC	40 ms 5,376 KB
testcase_14	AC	40 ms 5,376 KB
testcase_15	AC	40 ms 5,376 KB
testcase_16	AC	39 ms 5,376 KB
testcase_17	AC	39 ms 5,376 KB
testcase_18	AC	39 ms 5,376 KB
testcase_19	AC	39 ms 5,376 KB
testcase_20	AC	39 ms 5,376 KB
testcase_21	AC	39 ms 5,376 KB
testcase_22	AC	39 ms 5,376 KB
testcase_23	AC	28 ms 5,376 KB
testcase_24	AC	10 ms 5,376 KB
testcase_25	AC	24 ms 5,376 KB
testcase_26	AC	23 ms 5,376 KB
testcase_27	AC	38 ms 5,376 KB
testcase_28	AC	35 ms 5,376 KB
testcase_29	AC	6 ms 5,376 KB
testcase_30	AC	9 ms 5,376 KB
testcase_31	AC	29 ms 5,376 KB
testcase_32	AC	13 ms 5,376 KB
testcase_33	AC	24 ms 5,376 KB
testcase_34	AC	17 ms 5,376 KB
testcase_35	AC	39 ms 5,376 KB
testcase_36	AC	5 ms 5,376 KB
testcase_37	AC	34 ms 5,376 KB
testcase_38	AC	36 ms 5,376 KB
testcase_39	AC	23 ms 5,376 KB
testcase_40	AC	5 ms 5,376 KB
testcase_41	AC	7 ms 5,376 KB
testcase_42	AC	23 ms 5,376 KB
testcase_43	AC	1 ms 5,376 KB
testcase_44	AC	1 ms 5,376 KB
testcase_45	AC	1 ms 5,376 KB
testcase_46	AC	1 ms 5,376 KB
testcase_47	AC	1 ms 5,376 KB
testcase_48	AC	1 ms 5,376 KB
testcase_49	AC	1 ms 5,376 KB
testcase_50	AC	1 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	1 ms 5,376 KB
testcase_53	AC	1 ms 5,376 KB
testcase_54	AC	1 ms 5,376 KB
testcase_55	AC	1 ms 5,376 KB
testcase_56	AC	1 ms 5,376 KB
testcase_57	AC	1 ms 5,376 KB
testcase_58	AC	1 ms 5,376 KB
testcase_59	AC	1 ms 5,376 KB
testcase_60	AC	1 ms 5,376 KB
testcase_61	AC	1 ms 5,376 KB
testcase_62	AC	1 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <float.h>
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_MOD			1000000007								// 除数(10の9乗+7)
#define D_FACT_MAX		100005									// 最大階乗数

// 内部変数
static FILE *szpFpI;											// 入力
static int si1ModFact[D_FACT_MAX];								// 階乗リスト
static int si1ModFactR[D_FACT_MAX];								// 階乗リスト(逆元)

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
	static int siTNo;
#endif

// 出力
int
fOut(
	char *pcpLine				// <I> １行
)
{
	char lc1Buf[1024];

#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, pcpLine)) {
		siRes = -1;
	}
#else
	printf("%s", pcpLine);
#endif

	return 0;
}

// 階乗リスト - 作成
int
fMakeModFact(
	int piMax					// <I> 最大値
)
{
	int i;

	si1ModFact[0] = 1;
	si1ModFact[1] = 1;
	for (i = 2; i <= piMax; i++) {
		si1ModFact[i] = (int)((long long)si1ModFact[i - 1] * (long long)i % (long long)D_MOD);
	}

	return 0;
}

// べき乗 - 取得
int
fGetModPower(
	int piBase					// <I> 基数
	, int piIdx					// <I> 指数
)
{
	// 平方リスト - 作成
	int li1Val[100];
	li1Val[0] = piBase;
	int liCnt = 1;
	int liIdx = 1;
	while (piIdx > liIdx) {
		li1Val[liCnt] = (int)((long long)li1Val[liCnt - 1] * (long long)li1Val[liCnt - 1] % (long long)D_MOD);
		liCnt++;
		liIdx += liIdx;
	}

	// べき乗 - 取得
	int liVal = 1;
	while (piIdx > 0) {
		if (piIdx >= liIdx) {
			piIdx -= liIdx;
			liVal = (int)((long long)liVal * (long long)li1Val[liCnt - 1] % (long long)D_MOD);
		}
		liCnt--;
		liIdx /= 2;
	}

	return liVal;
}

// 階乗リスト(逆元) - 作成
int
fMakeModFactR(
	int piMax					// <I> 最大値
)
{
	int i;

	for (i = 0; i <= piMax; i++) {
		si1ModFactR[i] = fGetModPower(si1ModFact[i], D_MOD - 2);
	}

	return 0;
}

// 実行メイン
int
fMain(
)
{
	int i;
	char lc1Buf[1024];

	// 配列数 - 取得
	int liACnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &liACnt);

	// 階乗リスト - 作成
	fMakeModFact(liACnt);
	fMakeModFactR(liACnt);

	// 配列 - 取得
	long long llSum = 0;
	for (i = 0; i < liACnt; i++) {
		long long llVal;
		fscanf(szpFpI, "%lld", &llVal);

		// 二項係数 = n! / k! / (n-k)!
		long long llVal2 = si1ModFact[liACnt - 1];
		llVal2 = llVal2 * (long long)si1ModFactR[i] % (long long)D_MOD;
		llVal2 = llVal2 * (long long)si1ModFactR[liACnt - 1 - i] % (long long)D_MOD;

		// 加算
		llSum += llVal * llVal2;
		llSum %= D_MOD;
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	return (int)llSum;
}

// １回実行
int
fOne(
)
{
	int liRet;
	char lc1Buf[1024];

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", siTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", siTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 実行メイン
	liRet = fMain();

	// 出力
	sprintf(lc1Buf, "%d\n", liRet);
	fOut(lc1Buf);

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", siTNo);
	}
	else {
		printf("NG %d\n", siTNo);
	}
#endif

	return 0;
}

// プログラム開始
int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		siTNo = i;
		fOne();
	}
#else
	fOne();
#endif

	return 0;
}

yukicoder

結果

テストケース

ソースコード