# Chef and the Combination Lock SOLUTION CHEFSSM

Page Contents

### Chef and the Combination Lock November Challenge 2020

Chef has a combination lock with N wheels (numbered 1 through N). For each valid i, on the i-th wheel, the integers from 0 to Ai (inclusive) are written in ascending order (0 and Ai are also adjacent). Initially, one value on each wheel is selected uniformly randomly and independently.
The lock operates in a very peculiar way: it opens when there is at least one wheel where either 0 or the largest value on that wheel is selected. Chef wants to open the lock using the smallest possible number of operations; in one operation, he may choose one wheel and rotate it clockwise or counterclockwise by 1 unit (i.e. select a value that is adjacent to the previously selected value on that wheel).
Find the expected value of the number of operations which Chef needs to perform to open the lock.
The expected number of operations can be represented as a fraction PQ, where P is a non-negative integer and Q a positive integer coprime with 998,244,353. You should calculate P⋅Q−1 modulo 998,244,353, where Q−1 denotes the multiplicative inverse of Q modulo 998,244,353.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer P⋅Q−1 modulo 998,244,353.
Constraints
1≤T≤103
1≤N≤105
0≤Ai<998,244,353 for each valid i
the sum of N over all test cases does not exceed 105
N≤5,000
Ai≤5,000 for each valid i
the sum of N over all test cases does not exceed 5,000
N≤5,000
the sum of N over all test cases does not exceed 5,000
Subtask #3 (70 points): original constraints
Example Input
3
2
2 2
2
5 5
3
3 4 5
Example Output
443664157
221832079
598946612
SOLUTION :
from itertools import accumulate
C = 998244353
def sum(A, B):
return ((A % C) + (B % C)) % C
def prod(A, B):
return ((A % C) * (B % C)) % C
def get_X(A, M):
def f(a, b):
return prod(a, max(0, b + 1 – 2 * (M + 1)))
return tuple(accumulate([1] + A, f))[:-1]
def get_Y(A, M):
def f(a, b):
return prod(a, b + 1 – 2 * M)
return tuple(accumulate([1] + list(reversed(A)), f))[:-1]
T = int(input())
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
max_mosse = min(A) // 2
P = 0
for M in range(max_mosse+1):
p = 0
X = get_X(A, M)
Y = get_Y(A, M)
for i, x, y in zip(range(N), X, reversed(Y)):
F = min(2, A[i] + 1 – 2 * M)
p = (p + (((x * F) % C) * (y % C)) % C) % C
# print(f’X={X[i]}, F={F}, Y={Y[i]}, p={p}’)
P = (P + ((M * p) % C)) % C
# P = sum(P, prod(M, p))
Q = 1
for i in range(N):
Q = (Q * ((A[i] + 1) % C)) % C
print(prod(P, pow(Q, C-2, C)))