結果

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

ソースコード

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
print(ansM)
print(ansP)
0