(cache)Submission #76205739 - AtCoder Beginner Contest 448

Contest Duration: 2026-03-07(Sat) 21:00 - 2026-03-07(Sat) 22:40 (local time) (100 minutes) Back to Home

Submission #76205739

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
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#define MOD_BY 10007
int add(int a, int b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
int mul(int a, int b) {
  return a * b % MOD_BY;
}
struct next_s {
  int to_add, remainder;
};
int to_mul[32];
struct next_s next[10][11234][32];
int K, M;
int c[112345], l[112345];
int main(void) {
  int i, j, k;
  int ans = 0, remainder = 0;
  if (scanf("%d%d", &K, &M) != 2) return 1;
  for (i = 0; i < K; i++) {
    if (scanf("%d%d", &c[i], &l[i]) != 2) return 1;
  }
  for (i = 0; i <= 9; i++) {
    to_mul[0] = 10;
    for (j = 0; j < M; j++) {
      next[i][j][0] = (struct next_s){ (j * 10 + i) / M, (j * 10 + i) % M };
    }
    for (k = 1; k < 32; k++) {
      to_mul[k] = mul(to_mul[k - 1], to_mul[k - 1]);
      for (j = 0; j < M; j++) {
        struct next_s next_next = next[i][next[i][j][k - 1].remainder][k - 1];
        next[i][j][k] = (struct next_s) {
          add(mul(next[i][j][k - 1].to_add, to_mul[k - 1]), next_next.to_add),
          next_next.remainder
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MOD_BY 10007

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

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

struct next_s {
	int to_add, remainder;
};

int to_mul[32];
struct next_s next[10][11234][32];

int K, M;
int c[112345], l[112345];

int main(void) {
	int i, j, k;
	int ans = 0, remainder = 0;
	if (scanf("%d%d", &K, &M) != 2) return 1;
	for (i = 0; i < K; i++) {
		if (scanf("%d%d", &c[i], &l[i]) != 2) return 1;
	}
	for (i = 0; i <= 9; i++) {
		to_mul[0] = 10;
		for (j = 0; j < M; j++) {
			next[i][j][0] = (struct next_s){ (j * 10 + i) / M, (j * 10 + i) % M };
		}
		for (k = 1; k < 32; k++) {
			to_mul[k] = mul(to_mul[k - 1], to_mul[k - 1]);
			for (j = 0; j < M; j++) {
				struct next_s next_next = next[i][next[i][j][k - 1].remainder][k - 1];
				next[i][j][k] = (struct next_s) {
					add(mul(next[i][j][k - 1].to_add, to_mul[k - 1]), next_next.to_add),
					next_next.remainder
				};
			}
		}
	}
	for (i = 0; i < K; i++) {
		for (k = l[i], j = 0; j < 32; j++, k >>= 1) {
			if (k & 1) {
				struct next_s cur_next = next[c[i]][remainder][j];
				ans = add(mul(ans, to_mul[j]), cur_next.to_add);
				remainder = cur_next.remainder;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Submission Time	2026-05-29 21:56:38
Task	E - Simple Division
User	mikecat
Language	C23 (GCC 14.2.0)
Score	450
Code Size	1310 Byte
Status	AC
Exec Time	145 ms
Memory	27568 KiB

Judge Result

Set Name

Sample

All

Score / Max Score

0 / 0

450 / 450

Status

× 3

× 43

Set Name	Test Cases
Sample	sample_01.txt, sample_02.txt, sample_03.txt
All	hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt

Case Name	Status	Exec Time	Memory
hand_01.txt	AC	22 ms	26800 KiB
hand_02.txt	AC	22 ms	26688 KiB
hand_03.txt	AC	21 ms	26712 KiB
hand_04.txt	AC	26 ms	26564 KiB
hand_05.txt	AC	26 ms	26572 KiB
sample_01.txt	AC	0 ms	1752 KiB
sample_02.txt	AC	0 ms	1752 KiB
sample_03.txt	AC	26 ms	26696 KiB
test_01.txt	AC	0 ms	1884 KiB
test_02.txt	AC	15 ms	2516 KiB
test_03.txt	AC	36 ms	27568 KiB
test_04.txt	AC	21 ms	2520 KiB
test_05.txt	AC	21 ms	2588 KiB
test_06.txt	AC	36 ms	22984 KiB
test_07.txt	AC	96 ms	18904 KiB
test_08.txt	AC	25 ms	10460 KiB
test_09.txt	AC	59 ms	8540 KiB
test_10.txt	AC	145 ms	27480 KiB
test_11.txt	AC	43 ms	27460 KiB
test_12.txt	AC	44 ms	23624 KiB
test_13.txt	AC	36 ms	9820 KiB
test_14.txt	AC	28 ms	7488 KiB
test_15.txt	AC	91 ms	22856 KiB
test_16.txt	AC	43 ms	10632 KiB
test_17.txt	AC	22 ms	3672 KiB
test_18.txt	AC	43 ms	10588 KiB
test_19.txt	AC	88 ms	15692 KiB
test_20.txt	AC	64 ms	9668 KiB
test_21.txt	AC	47 ms	18860 KiB
test_22.txt	AC	34 ms	12296 KiB
test_23.txt	AC	89 ms	18204 KiB
test_24.txt	AC	34 ms	6488 KiB
test_25.txt	AC	29 ms	8412 KiB
test_26.txt	AC	94 ms	18480 KiB
test_27.txt	AC	121 ms	25036 KiB
test_28.txt	AC	79 ms	13148 KiB
test_29.txt	AC	77 ms	25668 KiB
test_30.txt	AC	23 ms	4676 KiB
test_31.txt	AC	54 ms	10156 KiB
test_32.txt	AC	92 ms	15300 KiB
test_33.txt	AC	89 ms	16068 KiB
test_34.txt	AC	57 ms	7832 KiB
test_35.txt	AC	39 ms	15660 KiB