#64112 (Python3) No.315 世界のなんとか3.5

• 問題: No.315 世界のなんとか3.5
• ユーザー: koyumeishi
• 提出日時: 2015-12-09 02:22:55
• 言語: Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1)
• 結果: TLE
• 実行時間: -
• コード長: 2,051 bytes
• コンパイル時間: 248 ms
• コンパイル使用メモリ: 12,928 KB
• 実行使用メモリ: 17,272 KB
• 最終ジャッジ日時: 2024-09-14 20:53:58
• 合計ジャッジ時間: 28,191 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 29 TLE * 1 -- * 6

ソースコード

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
import array
mod = 1000000007
a,b,p = input().split()
p = int(p)
memo = [[[] for col in range(8)] for row in range(10)]
def gen_memo():
    global memo
    for k in range(10) :
        for sml in range(2) :
            for mod3 in range(4) :
                s = (sml<<2)|mod3
                nx = [0 for i in range(8)]
                for d in range(10) :
                    if sml==0 and d>k :
                        continue
                    sml_ = 1 if (d<k or sml==1) else 0
                    mod3_ = 3 if (mod3==3 or d==3) else (mod3+d)%3
                    s_ = (sml_<<2) | mod3_
                    nx[s_] += 1
                for s_ in range(8) :
                    if nx[s_] > 0 :
                        memo[k][s].append( (s_, nx[s_]) )
def calc(x):
    sz = len(x)
    dp = [[[0 for col in range(8)] for row in range(p)] for hoge in range(2)]
    dp[0][0][0] = 1
    u = 0
    v = 1
    for i in range(sz) :
        k = ord(x[i]) - ord('0')
        for j in range(1 if i<sz-4 else p):
            for sml in range(2):
                for mod3 in range(4):
                    s = (sml<<2)|mod3
                    val = dp[u][j][s]
                    dp[u][j][s] = 0
                    if val == 0:
                        continue
                    if i<sz-5:
                        for c in range(len(memo[k][s])):
                            s_ = memo[k][s][c][0]
                            dp[v][0][ s_ ] += val * memo[k][s][c][1]
                            if dp[v][0][s_] >= mod:
                                dp[v][0][s_] %= mod
                    else:
                        for d in range(10) :
                            if sml==0 and d>k :
                                break
                            sml_ = 1 if (sml==1 or d<k) else 0
                            mod3_ = 3 if (mod3==3 or d==3) else (mod3+d)%3
                            s_ = (sml_<<2) | mod3_
                            j_ = (j*10 + d) % p
                            dp[v][j_][s_] += val
                            if dp[v][j_][s_] >= mod:
                                dp[v][j_][s_] -= mod
        u,v = v,u
    ret = 0
    for j in range(p) : 
        if j%p == 0 :
            continue
        for sml in range(2) :
            for mod3 in range(4) :
                if mod3==0 or mod3==3:
                    s = (sml<<2)|mod3
                    ret += dp[u][j][s];
                    ret += -mod if ret>=mod else 0
    return ret
gen_memo()
ans = calc(b)
ans = ans - calc(a)
ans += mod if ans<0 else 0
def hoge():
    global ans
    mod3__ = 0
    modp__ = 0
    for i in range(len(a)):
        k = ord(a[i])-ord('0')
        mod3__ = 3 if mod3__==3 or k==3 else (mod3__ + k)%3
        modp__ = (modp__ * 10 + k) % p
    if (mod3__==0 or mod3__==3) and modp__ != 0 :
        ans += 1
    ans %= mod
hoge()
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX