#813913 (PyPy3) No.189 SUPER HAPPY DAY

• 問題: No.189 SUPER HAPPY DAY
• ユーザー: terasa
• 提出日時: 2022-11-04 21:34:25
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 581 ms / 5,000 ms
• コード長: 3,657 bytes
• コンパイル時間: 119 ms
• コンパイル使用メモリ: 82,720 KB
• 実行使用メモリ: 108,288 KB
• 最終ジャッジ日時: 2024-07-18 19:17:27
• 合計ジャッジ時間: 7,165 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 23

ソースコード

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from typing import List, Tuple, Callable, TypeVar
import sys
import itertools
import heapq
import bisect
from collections import deque, defaultdict
from functools import lru_cache, cmp_to_key
input = sys.stdin.readline
# for AtCoder Easy test
if __file__ != 'prog.py':
    sys.setrecursionlimit(10 ** 6)
def readints(): return map(int, input().split())
def readlist(): return list(readints())
def readstr(): return input().rstrip()
T = TypeVar('T')
class Rerooting:
    # reference: https://null-mn.hatenablog.com/entry/2020/04/14/124151
    # 適当な頂点vを根とする部分木に対して計算される値dp_vが、vの子c1, c2, ... ckを用いて
    # 下記のように表すことができる
    # dp_v = g(merge(f(dp_c1,c1), f(dp_c2,c2), ..., f(dp_ck,ck)), v)
    def __init__(self, N: int, E: List[Tuple[int, int]],
                 f: Callable[[T, int, int, int], T],
                 g: Callable[[T, int], T],
                 merge: Callable[[T, T], T], e: T):
        self.N = N
        self.E = E
        self.f = f
        self.g = g
        self.merge = merge
        self.e = e
        self.dp = [[self.e for _ in range(len(self.E[v]))] for v in range(self.N)]
        self._calculate()
    def _dfs1(self, root):
        stack = [(root, -1)]
        ret = [self.e] * self.N
        while stack:
            v, p = stack.pop()
            if v < 0:
                v = ~v
                acc = self.e
                for i, (c, d) in enumerate(self.E[v]):
                    if d == p:
                        continue
                    self.dp[v][i] = ret[d]
                    acc = self.merge(acc, self.f(ret[d], v, d, c))
                ret[v] = self.g(acc, v)
                continue
            stack.append((~v, p))
            for i, (c, d) in enumerate(self.E[v]):
                if d == p:
                    continue
                stack.append((d, v))
    def _dfs2(self, root):
        stack = [(root, -1, self.e)]
        while stack:
            v, p, from_par = stack.pop()
            for i, (c, d) in enumerate(self.E[v]):
                if d == p:
                    self.dp[v][i] = from_par
                    break
            ch = len(self.E[v])
            Sr = [self.e] * (ch + 1)
            for i in range(ch, 0, -1):
                c, d = self.E[v][i - 1]
                Sr[i - 1] = self.merge(Sr[i], self.f(self.dp[v][i - 1], v, d, c))
            Sl = self.e
            for i, (c, d) in enumerate(self.E[v]):
                if d != p:
                    val = self.merge(Sl, Sr[i + 1])
                    stack.append((d, v, self.g(val, v)))
                Sl = self.merge(Sl, self.f(self.dp[v][i], v, d, c))
    def _calculate(self, root=0):
        self._dfs1(root)
        self._dfs2(root)
    def solve(self, v):
        ans = self.e
        for i, (c, d) in enumerate(self.E[v]):
            ans = self.merge(ans, self.f(self.dp[v][i], v, d, c))
        return self.g(ans, v)
M, D = input().split()
mod = 10 ** 9 + 9
def solve(n):
    dp = [[0, 0] for _ in range(L + 1)]
    dp[0][0] = 1
    for i in range(len(n)):
        ndp = [[0, 0] for _ in range(L + 1)]
        for j in range(L + 1):
            for k in range(10):
                if j - k < 0:
                    break
                ndp[j][1] += dp[j - k][1]
                if k < int(n[i]):
                    ndp[j][1] += dp[j - k][0]
                elif k == int(n[i]):
                    ndp[j][0] += dp[j - k][0]
        dp = ndp
    return dp
L = 2000
dpm = solve(M)
dpd = solve(D)
ans = 0
for i in range(1, L + 1):
    ans += sum(dpm[i]) * sum(dpd[i]) % mod
    ans %= mod
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX