(cache)Submission #69953431 - UNIQUE VISION Programming Contest 2025 Autumn (AtCoder Beginner Contest 425)

Contest Duration: 2025-09-27(Sat) 21:00 - 2025-09-27(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #69953431

Source Code Expand

Copy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define MAX 5050
int sosuu_cnt;
int sosuu_list[MAX];
char is_not_sosuu[MAX];
int sosuu_pos[MAX];
int soinsu_cnt[MAX];
int soinsu[MAX][16];
int soinsu_rui[MAX][MAX];
void init(void) {
  int i, j;
  is_not_sosuu[0] = is_not_sosuu[1] = 1;
  for (i = 2; i < MAX; i++) {
    if (!is_not_sosuu[i]) {
      sosuu_pos[i] = sosuu_cnt;
      sosuu_list[sosuu_cnt++] = i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MAX 5050

int sosuu_cnt;
int sosuu_list[MAX];
char is_not_sosuu[MAX];
int sosuu_pos[MAX];

int soinsu_cnt[MAX];
int soinsu[MAX][16];

int soinsu_rui[MAX][MAX];

void init(void) {
	int i, j;
	is_not_sosuu[0] = is_not_sosuu[1] = 1;
	for (i = 2; i < MAX; i++) {
		if (!is_not_sosuu[i]) {
			sosuu_pos[i] = sosuu_cnt;
			sosuu_list[sosuu_cnt++] = i;
			for (j = i * i; j < MAX; j += i) is_not_sosuu[j] = 1;
		}
	}
	for (i = 2; i < MAX; i++) {
		int cur = i;
		for (j = 2; j * j <= cur; j++) {
			while (cur % j == 0) {
				soinsu[i][soinsu_cnt[i]++] = j;
				cur /= j;
			}
		}
		if (cur > 1) soinsu[i][soinsu_cnt[i]++] = cur;
		for (j = 0; j < soinsu_cnt[i]; j++) {
			soinsu_rui[i][sosuu_pos[soinsu[i][j]]]++;
		}
		for (j = 0; j < sosuu_cnt; j++) {
			soinsu_rui[i][j] += soinsu_rui[i - 1][j];
		}
	}
}

int T, M;
int N;
int C[312345];

int main(void) {
	int tc;
	init();
	if (scanf("%d%d", &T, &M) != 2) return 1;
	for (tc = 1; tc <= T; tc++) {
		int i, j;
		int sum = 0;
		int ans = 1;
		if (scanf("%d", &N) != 1) return 1;
		for (i = 0; i < N; i++) {
			if (scanf("%d", &C[i]) != 1) return 1;
			sum += C[i];
		}
		for (i = 0; i < sosuu_cnt; i++) {
			int cnt = soinsu_rui[sum][i];
			for (j = 0; j < N; j++) cnt -= soinsu_rui[C[j]][i];
			for (j = 0; j < cnt; j++) ans = (int)((long long)ans * sosuu_list[i] % M);
		}
		printf("%d\n", ans);
	}
	return 0;
}

Submission Info

Submission Time	2025-10-08 08:16:45
Task	E - Count Sequences 2
User	mikecat
Language	C (gcc 12.2.0)
Score	450
Code Size	1456 Byte
Status	AC
Exec Time	488 ms
Memory	35612 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 2

× 51

Set Name	Test Cases
Sample	00_sample_00.txt, 00_sample_01.txt
All	00_sample_00.txt, 00_sample_01.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt, 01_test_33.txt, 01_test_34.txt, 01_test_35.txt, 01_test_36.txt, 01_test_37.txt, 01_test_38.txt, 01_test_39.txt, 01_test_40.txt, 01_test_41.txt, 01_test_42.txt, 01_test_43.txt, 01_test_44.txt, 01_test_45.txt, 01_test_46.txt, 01_test_47.txt, 01_test_48.txt

Case Name	Status	Exec Time	Memory
00_sample_00.txt	AC	14 ms	35500 KiB
00_sample_01.txt	AC	14 ms	35480 KiB
01_test_00.txt	AC	153 ms	35444 KiB
01_test_01.txt	AC	256 ms	35596 KiB
01_test_02.txt	AC	229 ms	35504 KiB
01_test_03.txt	AC	152 ms	35460 KiB
01_test_04.txt	AC	258 ms	35416 KiB
01_test_05.txt	AC	231 ms	35488 KiB
01_test_06.txt	AC	153 ms	35516 KiB
01_test_07.txt	AC	257 ms	35416 KiB
01_test_08.txt	AC	233 ms	35600 KiB
01_test_09.txt	AC	152 ms	35436 KiB
01_test_10.txt	AC	255 ms	35420 KiB
01_test_11.txt	AC	230 ms	35480 KiB
01_test_12.txt	AC	152 ms	35500 KiB
01_test_13.txt	AC	255 ms	35580 KiB
01_test_14.txt	AC	230 ms	35504 KiB
01_test_15.txt	AC	151 ms	35604 KiB
01_test_16.txt	AC	257 ms	35596 KiB
01_test_17.txt	AC	229 ms	35596 KiB
01_test_18.txt	AC	151 ms	35496 KiB
01_test_19.txt	AC	258 ms	35588 KiB
01_test_20.txt	AC	231 ms	35436 KiB
01_test_21.txt	AC	151 ms	35596 KiB
01_test_22.txt	AC	255 ms	35496 KiB
01_test_23.txt	AC	233 ms	35500 KiB
01_test_24.txt	AC	151 ms	35492 KiB
01_test_25.txt	AC	254 ms	35456 KiB
01_test_26.txt	AC	229 ms	35476 KiB
01_test_27.txt	AC	152 ms	35608 KiB
01_test_28.txt	AC	257 ms	35572 KiB
01_test_29.txt	AC	230 ms	35460 KiB
01_test_30.txt	AC	151 ms	35604 KiB
01_test_31.txt	AC	255 ms	35560 KiB
01_test_32.txt	AC	230 ms	35568 KiB
01_test_33.txt	AC	151 ms	35464 KiB
01_test_34.txt	AC	255 ms	35588 KiB
01_test_35.txt	AC	230 ms	35496 KiB
01_test_36.txt	AC	152 ms	35496 KiB
01_test_37.txt	AC	255 ms	35488 KiB
01_test_38.txt	AC	232 ms	35584 KiB
01_test_39.txt	AC	152 ms	35512 KiB
01_test_40.txt	AC	256 ms	35496 KiB
01_test_41.txt	AC	230 ms	35592 KiB
01_test_42.txt	AC	152 ms	35516 KiB
01_test_43.txt	AC	255 ms	35484 KiB
01_test_44.txt	AC	229 ms	35496 KiB
01_test_45.txt	AC	152 ms	35612 KiB
01_test_46.txt	AC	255 ms	35504 KiB
01_test_47.txt	AC	229 ms	35580 KiB
01_test_48.txt	AC	488 ms	35576 KiB