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
| from typing import Any, Callable, Dict, List, Optional, Tuple, TypeVar, Union
from sys import exit, setrecursionlimit, stdin
from string import ascii_lowercase, ascii_uppercase
from math import ceil, comb, fabs, floor, gcd, hypot, log, perm, sqrt
from itertools import combinations, compress, permutations, starmap, tee
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from functools import lru_cache, reduce
from datetime import datetime, timedelta
from collections import Counter, defaultdict, deque
import random
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)
setrecursionlimit(int(2e9))
class Arr:
array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
graph = staticmethod(lambda size=N: [[] for _ in range(size)])
class Math:
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
class IO:
input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
read = staticmethod(lambda: map(int, IO.input().split()))
read_list = staticmethod(lambda: list(IO.read()))
class Std:
pass
class Solution:
def countDigitOne(self, n: int) -> int:
s = str(n)
@lru_cache(None)
def dfs(i, cnt, is_limit, is_num):
if i == len(s):
return cnt
res = 0
if not is_num:
res = dfs(i + 1, cnt, False, False)
up = int(s[i]) if is_limit else 9
down = 0 if is_num else 1
for d in range(down, up + 1):
res += dfs(i + 1, cnt + (d == 1), is_limit and d == up, True)
return res
return dfs(0, 0, True, False)
|