Submission #67266013


Source Code Expand

Copy
#include <stdio.h>
#include <stdlib.h>
#define MOD_BY 998244353
#define INV_6 166374059
int add(int a, int b) {
return a + b - MOD_BY * (a + b >= MOD_BY);
}
int sub(int a, int b) {
return b == 0 ? a : add(a, MOD_BY - b);
}
int mul(int a, int b) {
return (int)((long long)a * b % MOD_BY);
}
int pou(int a, int b) {
int r = 1;
while (b > 0) {
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <stdio.h>
#include <stdlib.h>

#define MOD_BY 998244353
#define INV_6 166374059

int add(int a, int b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

int sub(int a, int b) {
	return b == 0 ? a : add(a, MOD_BY - b);
}

int mul(int a, int b) {
	return (int)((long long)a * b % MOD_BY);
}

int pou(int a, int b) {
	int r = 1;
	while (b > 0) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}

int N;
int A[114514][6];

struct meow {
	int value;
	int idx;
};

int cmp(const void* x, const void* y) {
	struct meow a = *(const struct meow*)x, b = *(const struct meow*)y;
	return a.value < b.value ? -1 : a.value > b.value;
}

struct meow nyan[114514 * 6];

int dice_used[114514];
int used_counts[7];

int main(void) {
	int i, j;
	int ans = 0;
	int prev_prob = 0;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 0; i < N; i++) {
		for (j = 0; j < 6; j++) {
			if (scanf("%d", &A[i][j]) != 1) return 1;
			nyan[i * 6 + j] = (struct meow){ A[i][j], i };
		}
	}
	qsort(nyan, N * 6, sizeof(*nyan), cmp);
	used_counts[0] = N;
	for (i = 0; i < N * 6; i++) {
		used_counts[dice_used[nyan[i].idx]]--;
		dice_used[nyan[i].idx]++;
		used_counts[dice_used[nyan[i].idx]]++;
		if (nyan[i].value != nyan[i + 1].value) {
			int prob = 1;
			for (j = 0; j <= 6; j++) {
				prob = mul(prob, pou(j, used_counts[j]));
			}
			ans = add(ans, mul(sub(prob, prev_prob), nyan[i].value % MOD_BY));
			prev_prob = prob;
		}
	}
	printf("%d\n", mul(ans, pou(INV_6, N)));
	return 0;
}

/*

下からやる

「最大値がそれ以下の確率」から「最大値がそれ未満の確率」を引く
→「最大値がそれの確率」になる

*/

Submission Info

Submission Time
Task E - E [max]
User mikecat
Language C (gcc 12.2.0)
Score 450
Code Size 1733 Byte
Status AC
Exec Time 298 ms
Memory 13200 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 3
AC × 26
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 02_random2_05.txt, 02_random2_06.txt, 03_handmade_00.txt, 03_handmade_01.txt, 03_handmade_02.txt, 03_handmade_03.txt, 03_handmade_04.txt, 03_handmade_05.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 1736 KiB
00_sample_01.txt AC 1 ms 1732 KiB
00_sample_02.txt AC 0 ms 1624 KiB
01_random_00.txt AC 25 ms 2608 KiB
01_random_01.txt AC 296 ms 13132 KiB
01_random_02.txt AC 168 ms 8356 KiB
01_random_03.txt AC 296 ms 13120 KiB
01_random_04.txt AC 3 ms 1800 KiB
01_random_05.txt AC 297 ms 13004 KiB
01_random_06.txt AC 150 ms 7564 KiB
01_random_07.txt AC 298 ms 13200 KiB
01_random_08.txt AC 254 ms 11528 KiB
01_random_09.txt AC 297 ms 13112 KiB
02_random2_00.txt AC 63 ms 10760 KiB
02_random2_01.txt AC 97 ms 12884 KiB
02_random2_02.txt AC 112 ms 13152 KiB
02_random2_03.txt AC 124 ms 13136 KiB
02_random2_04.txt AC 135 ms 13116 KiB
02_random2_05.txt AC 167 ms 13172 KiB
02_random2_06.txt AC 190 ms 13192 KiB
03_handmade_00.txt AC 1 ms 1644 KiB
03_handmade_01.txt AC 1 ms 1768 KiB
03_handmade_02.txt AC 1 ms 1756 KiB
03_handmade_03.txt AC 70 ms 12896 KiB
03_handmade_04.txt AC 174 ms 13124 KiB
03_handmade_05.txt AC 193 ms 13168 KiB


2025-07-04 (Fri)
07:55:08 +09:00