結果

問題 No.528 10^9と10^9+7と回文
ユーザー tktk_snsn
提出日時 2021-02-10 21:29:47
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,319 bytes
コンパイル時間 647 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 114,688 KB
最終ジャッジ日時 2024-07-08 08:40:55
合計ジャッジ時間 7,241 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

S = input()
N = len(S)
if N == 1:
    print(S)
    print(S)
    exit()

M = 10 ** 9
P = 10 ** 9 + 7

ansM = 0
ansP = 0
for i in range(1, N):
    ansM += 9 * pow(10, (i-1)//2, M)
    ansM %= M
    ansP += 9 * pow(10, (i-1)//2, P)
    ansP %= P


size = (N + 1) // 2
dpM = [[[0] * 10 for _ in range(2)] for _ in range(size + 1)]
dpP = [[[0] * 10 for _ in range(2)] for _ in range(size + 1)]
dpM[0][0][0] = 1
dpP[0][0][0] = 1
for i in range(size):
    if i == 0:
        rng = range(1, 10)
    else:
        rng = range(10)
    nF = int(S[i])
    nL = int(S[size - i - 1])
    for j in range(2):
        for k in range(10):
            for d in rng:
                ni = i + 1
                nj = j
                nk = d
                if nj == 0:
                    if d > nF:
                        continue
                    if d > nL:
                        continue
                    if d < nF:
                        nj = 1
                dpM[ni][nj][nk] += dpM[i][j][k]
                dpM[ni][nj][nk] %= M
                dpP[ni][nj][nk] += dpP[i][j][k]
                dpP[ni][nj][nk] %= P

for i in range(2):
    for j in range(10):
        ansM += dpM[size][i][j]
        ansM %= M
        ansP += dpP[size][i][j]
        ansP %= P
ansM = (ansM - 1) % M
ansP = (ansP - 1) % P
print(ansM)
print(ansP)
0