結果
問題 | No.434 占い |
ユーザー | Navier_Boltzmann |
提出日時 | 2024-11-01 19:53:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 16,269 bytes |
コンパイル時間 | 359 ms |
コンパイル使用メモリ | 82,464 KB |
実行使用メモリ | 80,288 KB |
最終ジャッジ日時 | 2024-11-01 19:53:50 |
合計ジャッジ時間 | 7,813 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 55 ms
66,320 KB |
testcase_01 | WA | - |
testcase_02 | AC | 55 ms
66,384 KB |
testcase_03 | AC | 59 ms
66,280 KB |
testcase_04 | AC | 59 ms
66,564 KB |
testcase_05 | AC | 56 ms
67,244 KB |
testcase_06 | WA | - |
testcase_07 | AC | 66 ms
71,132 KB |
testcase_08 | AC | 91 ms
78,092 KB |
testcase_09 | AC | 90 ms
78,116 KB |
testcase_10 | AC | 106 ms
78,096 KB |
testcase_11 | AC | 162 ms
79,644 KB |
testcase_12 | WA | - |
testcase_13 | AC | 117 ms
78,312 KB |
testcase_14 | AC | 112 ms
78,012 KB |
testcase_15 | AC | 166 ms
79,824 KB |
testcase_16 | AC | 179 ms
79,344 KB |
testcase_17 | AC | 154 ms
78,192 KB |
testcase_18 | AC | 223 ms
78,348 KB |
testcase_19 | AC | 256 ms
80,288 KB |
testcase_20 | WA | - |
testcase_21 | AC | 179 ms
79,580 KB |
testcase_22 | AC | 225 ms
79,796 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 181 ms
79,504 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
ソースコード
# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')from collections import *from functools import *from heapq import *from itertools import *import sys, math,random# input = sys.stdin.buffer.readline# sys.setrecursionlimit(10**6)def cle(a, D):"""Counts the number of elements in D that are less than or equal to a.Parameters:a (int): The value to compare against.D (list): A sorted list of integers.Returns:int: The count of elements in D that are less than or equal to a."""y = len(D) - 1x = 0if D[x] > a:return 0if D[y] <= a:return y + 1while y - x > 1:mid = (y + x) // 2if D[mid] <= a:x = midelse:y = midreturn yclass cs_2d:"""2D cumulative sum class."""def __init__(self, x):"""Initializes the 2D cumulative sum array.Parameters:x (list of list of int): A 2D list of integers."""n = len(x)m = len(x[0])self.n = nself.m = mtmp = [0] * ((n + 1) * (m + 1))for i in range(n):for j in range(m):tmp[m * (i + 1) + j + 1] = (tmp[m * (i + 1) + j] + tmp[m * i + j + 1] - tmp[m * i + j] + x[i][j])self.S = tmpdef query(self, ix, jx, iy, jy):"""Queries the sum of the submatrix from (ix, iy) to (jx, jy).Parameters:ix (int): Starting row index.jx (int): Ending row index.iy (int): Starting column index.jy (int): Ending column index.Returns:int: The sum of the submatrix."""return (self.S[self.m * jx + jy]- self.S[self.m * jx + iy]- self.S[self.m * ix + jy]+ self.S[self.m * ix + iy])class prime_factorize:"""Class for prime factorization and related operations."""def __init__(self, M=10**6):"""Initializes the sieve for prime factorization.Parameters:M (int): The maximum number to factorize."""self.sieve = [-1] * (M + 1)self.sieve[1] = 1self.p = [False] * (M + 1)self.mu = [1] * (M + 1)for i in range(2, M + 1):if self.sieve[i] == -1:self.p[i] = Truei2 = i**2for j in range(i2, M + 1, i2):self.mu[j] = 0for j in range(i, M + 1, i):self.sieve[j] = iself.mu[j] *= -1def factors(self, x):"""Returns the prime factors of x.Parameters:x (int): The number to factorize.Returns:list: A list of prime factors of x."""tmp = []while self.sieve[x] != x:tmp.append(self.sieve[x])x //= self.sieve[x]tmp.append(self.sieve[x])return tmpdef divisors(self, x):"""Returns all divisors of x.Parameters:x (int): The number to find divisors for.Returns:list: A sorted list of all divisors of x."""C = Counter(self.factors(x))tmp = []for p in product(*[[pow(k, i) for i in range(v + 1)] for k, v in C.items()]):res = 1for pp in p:res *= pptmp.append(res)tmp.sort()return tmpdef is_prime(self, x):"""Checks if x is a prime number.Parameters:x (int): The number to check.Returns:bool: True if x is prime, False otherwise."""return self.p[x]def mobius(self, x):"""Returns the Möbius function value of x.Parameters:x (int): The number to find the Möbius function value for.Returns:int: The Möbius function value of x."""return self.mu[x]class combination:"""Class for computing combinations (nCr) modulo p."""def __init__(self, N, p):"""Initializes the combination class.Parameters:N (int): The maximum value of n.p (int): The modulus."""self.fact = [1, 1] # fact[n] = (n! mod p)self.factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p)self.inv = [0, 1] # factinv calculationself.p = pfor i in range(2, N + 1):self.fact.append((self.fact[-1] * i) % p)self.inv.append((-self.inv[p % i] * (p // i)) % p)self.factinv.append((self.factinv[-1] * self.inv[-1]) % p)def cmb(self, n, r):"""Computes the combination (nCr) modulo p.Parameters:n (int): The total number of items.r (int): The number of items to choose.Returns:int: The value of nCr modulo p."""if (r < 0) or (n < r):return 0r = min(r, n - r)return self.fact[n] * self.factinv[r] * self.factinv[n - r] % self.pdef md(n):"""Returns all divisors of n.Parameters:n (int): The number to find divisors for.Returns:list: A sorted list of all divisors of n."""lower_divisors, upper_divisors = [], []i = 1while i * i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n // i)i += 1return lower_divisors + upper_divisors[::-1]class DSU:"""Disjoint Set Union (Union-Find) class."""def __init__(self, n):"""Initializes the DSU.Parameters:n (int): The number of elements."""self._n = nself.parent_or_size = [-1] * nself.member = [[i] for i in range(n)]self._max = [i for i in range(n)]self._min = [i for i in range(n)]def merge(self, a, b):"""Merges the sets containing a and b.Parameters:a (int): An element in the first set.b (int): An element in the second set.Returns:int: The leader of the merged set."""assert 0 <= a < self._nassert 0 <= b < self._nx, y = self.leader(a), self.leader(b)if x == y:return xif -self.parent_or_size[x] < -self.parent_or_size[y]:x, y = y, xself.parent_or_size[x] += self.parent_or_size[y]self._max[x] = max(self._max[x],self._max[y])self._min[x] = min(self._min[x],self._min[y])for tmp in self.member[y]:self.member[x].append(tmp)self.parent_or_size[y] = xreturn xdef get_max(self,x):return self._max[self.leader(x)]def get_min(self,x):return self._min[self.leader(x)]def members(self, a):"""Returns the members of the set containing a.Parameters:a (int): An element in the set.Returns:list: A list of members in the set containing a."""return self.member[self.leader(a)]def same(self, a, b):"""Checks if a and b are in the same set.Parameters:a (int): An element in the first set.b (int): An element in the second set.Returns:bool: True if a and b are in the same set, False otherwise."""assert 0 <= a < self._nassert 0 <= b < self._nreturn self.leader(a) == self.leader(b)def leader(self, a):"""Finds the leader of the set containing a.Parameters:a (int): An element in the set.Returns:int: The leader of the set containing a."""assert 0 <= a < self._nif self.parent_or_size[a] < 0:return aself.parent_or_size[a] = self.leader(self.parent_or_size[a])return self.parent_or_size[a]def size(self, a):"""Returns the size of the set containing a.Parameters:a (int): An element in the set.Returns:int: The size of the set containing a."""assert 0 <= a < self._nreturn -self.parent_or_size[self.leader(a)]def groups(self):"""Returns all sets as a list of lists.Returns:list: A list of lists, where each list contains the members of a set."""leader_buf = [self.leader(i) for i in range(self._n)]result = [[] for _ in range(self._n)]for i in range(self._n):result[leader_buf[i]].append(i)return [r for r in result if r != []]class SegTree:"""Segment Tree class."""def __init__(self, init_val, segfunc, ide_ele):"""Initializes the Segment Tree.Parameters:init_val (list): The initial values for the leaves of the tree.segfunc (function): The function to use for segment operations.ide_ele (any): The identity element for the segment function."""n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.num# Set the initial values to the leavesfor i in range(n):self.tree[self.num + i] = init_val[i]# Build the treefor i in range(self.num - 1, 0, -1):self.tree[i] = segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):"""Updates the k-th value to x.Parameters:k (int): The index to update (0-indexed).x (any): The new value."""k += self.numself.tree[k] = xwhile k > 1:tk = k >> 1self.tree[tk] = self.segfunc(self.tree[tk << 1], self.tree[(tk << 1) + 1])k >>= 1def get(self, x):return self.tree[x + self.num]def query(self, l, r):"""Queries the segment function result for the range [l, r).Parameters:l (int): The start index (0-indexed).r (int): The end index (0-indexed).Returns:any: The result of the segment function for the range [l, r)."""res_l = self.ide_eleres_r = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res_l = self.segfunc(res_l, self.tree[l])l += 1if r & 1:res_r = self.segfunc(self.tree[r - 1], res_r)l >>= 1r >>= 1res = self.segfunc(res_l, res_r)return resclass RSQandRAQ():"""区間加算、区間取得クエリをそれぞれO(logN)で答えるadd: 区間[l, r)にvalを加えるquery: 区間[l, r)の和を求めるl, rは0-indexed"""def __init__(self, n, mod=None):self.n = nself.bit0 = [0] * (n + 1)self.bit1 = [0] * (n + 1)self.mod = moddef _add(self, bit, i, val):i = i + 1while i <= self.n:if self.mod is None:bit[i] += valelse:bit[i] = (bit[i]+val)%self.modi += i & -idef _get(self, bit, i):s = 0while i > 0:if self.mod is None:s += bit[i]else:s = (s + bit[i])%self.modi-= i & -ireturn sdef add(self, l, r, val):"""区間[l, r)にvalを加える"""self._add(self.bit0, l, -val * l)self._add(self.bit0, r, val * r)self._add(self.bit1, l, val)self._add(self.bit1, r, -val)def query(self, l, r):"""区間[l, r)の和を求める"""_res = (self._get(self.bit0, r) + r * self._get(self.bit1, r)- self._get(self.bit0, l) - l * self._get(self.bit1, l) )if self.mod is None:return _reselse:return _res%self.modclass Dinic:def __init__(self, n):self.n = nself.links = [[] for _ in range(n)]self.depth = Noneself.progress = Nonedef add_link(self, _from, to, cap):self.links[_from].append([cap, to, len(self.links[to])])self.links[to].append([0, _from, len(self.links[_from]) - 1])def bfs(self, s):depth = [-1] * self.ndepth[s] = 0q = deque([s])while q:v = q.popleft()for cap, to, rev in self.links[v]:if cap > 0 and depth[to] < 0:depth[to] = depth[v] + 1q.append(to)self.depth = depthdef dfs(self, v, t, flow):if v == t:return flowlinks_v = self.links[v]for i in range(self.progress[v], len(links_v)):self.progress[v] = icap, to, rev = link = links_v[i]if cap == 0 or self.depth[v] >= self.depth[to]:continued = self.dfs(to, t, min(flow, cap))if d == 0:continuelink[0] -= dself.links[to][rev][0] += dreturn dreturn 0def max_flow(self, s, t):flow = 0while True:self.bfs(s)if self.depth[t] < 0:return flowself.progress = [0] * self.ncurrent_flow = self.dfs(s, t, float('inf'))while current_flow > 0:flow += current_flowcurrent_flow = self.dfs(s, t, float('inf'))def modinv(a,MOD):r0,r1,s0,s1 = a,MOD,1,0while r1:r0,r1, s0,s1 = r1,r0%r1, s1,s0-r0//r1*s1return s0%MODdef factorize(N):factorization = []for i in range(2,N+1):if i*i > N: breakif N%i: continuec = 0while N%i == 0:N //= ic += 1factorization.append((i,i**c))if N != 1: factorization.append((N,N))return factorizationclass BinomialCoefficient:def __init__(self,m):self.MOD = mself.factorization = factorize(m)self.facs = []self.invs = []self.coeffs = []self.pows = []for p,pe in self.factorization:fac = [1]*pefor i in range(1,pe):fac[i] = fac[i-1]*(i if i%p else 1)%peinv = [1]*peinv[-1] = fac[-1]for i in range(1,pe)[::-1]:inv[i-1] = inv[i]*(i if i%p else 1)%peself.facs.append(fac)self.invs.append(inv)# coeffsc = modinv(m//pe,pe)self.coeffs.append(m//pe*c%m)# powspowp = [1]while powp[-1]*p != pe:powp.append(powp[-1]*p)self.pows.append(powp)def choose(self,n,k):if k < 0 or k > n: return 0if k == 0 or k == n: return 1%self.MODres = 0for i,(p,pe) in enumerate(self.factorization):res += self._choose_pe(n,k,p,pe,self.facs[i],self.invs[i],self.pows[i]) * self.coeffs[i]res %= self.MODreturn resdef _E(self,n,k,r,p):res = 0while n:n //= pk //= pr //= pres += n - k - rreturn resdef _choose_pe(self,n,k,p,pe,fac,inv,powp):r = n-ke0 = self._E(n,k,r,p)if e0 >= len(powp): return 0res = powp[e0]if (p != 2 or pe == 4) and self._E(n//(pe//p),k//(pe//p),r//(pe//p),p)%2:res = pe-reswhile n:res = res * fac[n%pe]%pe * inv[k%pe]%pe * inv[r%pe]%pen //= pk //= pr //= preturn resdef answer():S = list(input())C = BinomialCoefficient(9)S = [int(s) for s in S]ans = 0N = len(S)for i,s in enumerate(S):ans = (ans + s*C.choose(N-1,i))%9if ans==0:ans = 9print(ans)for _ in range(int(input())):answer()