結果
問題 | No.2437 Fragile Multiples of 11 |
ユーザー |
|
提出日時 | 2023-08-19 00:06:00 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 83 ms / 2,000 ms |
コード長 | 2,674 bytes |
コンパイル時間 | 161 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 76,808 KB |
最終ジャッジ日時 | 2024-11-28 11:59:27 |
合計ジャッジ時間 | 3,599 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 34 |
ソースコード
import sysfrom itertools import permutationsfrom heapq import *input = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())class SegmentTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numself.size = nfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):k += self.numself.tree[k] = self.segfunc(self.tree[k],x)while k > 1:k >>= 1self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])def query(self, l, r):if r==self.size:r = self.numres = self.ide_elel += self.numr += self.numright = []while l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:right.append(self.tree[r-1])l >>= 1r >>= 1for e in right[::-1]:res = self.segfunc(res,e)return resmod = 998244353M = 110ans = [0] * (M+1)for k in range(1,M+1):dp = [[0]*11 for i in range(k)]for d in range(1,10):dp[0][d] = 1for i in range(1,k):for pre_m in range(11):for d in range(10):if (2*pre_m-d)%11:dp[i][(d-pre_m)%11] += dp[i-1][pre_m]dp[i][(d-pre_m)%11] %= modans[k] = dp[k-1][0]N = int(input())X = str(int(input())+1)N = len(X)res = 0for k in range(1,N):res += ans[k]dp = [[[0]*11 for i in range(N)] for p in range(2)]for d in range(1,int(X[0])):dp[1][0][d] = 1dp[0][0][int(X[0])] = 1for i in range(1,N):x = int(X[i])for d in range(x):for pre_m in range(11):if ((2*pre_m-d)%11!=0):dp[1][i][(d-pre_m)%11] += dp[0][i-1][pre_m]dp[1][i][(d-pre_m)%11] += dp[1][i-1][pre_m]dp[1][i][(d-pre_m)%11] %= modfor d in range(x,10):for pre_m in range(11):if ((2*pre_m-d)%11!=0):if d == x:dp[0][i][(d-pre_m)%11] += dp[0][i-1][pre_m]dp[1][i][(d-pre_m)%11] += dp[1][i-1][pre_m]dp[0][i][(d-pre_m)%11] %= moddp[1][i][(d-pre_m)%11] %= modres += dp[1][N-1][0]res %= modprint(res)