No.3415 Dial Lock
タグ : / 解いたユーザー数 11
作問者 :
risujiroh
Problem Statement
There is a dial lock with $N$ digits.
Each dial can display any one of $0, 1, \dots, 9$.
Initially, the lock is locked and all dials display $0$.
The dial lock can be unlocked by pulling its shackle while, for all $1 \le i \leq N$, the $i$-th digit from the left is $A_i$.
Here, it is guaranteed that $\max(A_1, A_2, \dots, A_N) \neq 0$.
Alice wants to unlock the dial lock, but she does not know the combination $A_1, A_2, \dots, A_N$.
So Alice decided to try the following sequence of operations at most $T$ times.
- $K$ strategies are given in advance. The $i$-th strategy is represented by a sequence of non-negative integers $(R_{i,1}, R_{i,2}, \dots, R_{i,N})$.
-
During an operation, Alice chooses an integer $i$ between $1$ and $K$, inclusive, uniformly at random.
Then, for $j=1,2,\dots,N$, she turns the $j$-th dial $R_{i,j}$ times in the forward direction.
- In other words, letting $c_j$ be the number currently displayed by the $j$-th dial, she makes each dial display $(c_j + R_{i,j}) \bmod 10$ for $j=1,2,\dots,N$.
- Then, Alice pulls the shackle and tries to see whether the dial lock can be unlocked. If she succeeds in unlocking it, she performs no further operations.
Alice keeps performing operations as long as she is able to, but if she has not unlocked the lock after performing $T$ operations, she gives up on unlocking it.
Find the probability that Alice succeeds in unlocking the lock, $\text{mod }120586241$ ($=2^{20}\times 115+1$, a prime).
What is a rational number $\text{mod }120586241$?
It can be proved that the desired probability is always a rational number.Moreover, under the constraints of this problem, when the value is expressed as $\frac{P}{Q}$ using $2$ coprime integers $P$, $Q$, it can be proved that there exists exactly one integer $R$ satisfying $R \times Q \equiv P\pmod{120586241}$ and $0 \leq R \lt 120586241$. Find this $R$.
Constraints
- $1 \leq N \leq 5$
- $1 \leq K \leq 10^N - 1$
- $1 \leq T \leq 10^9$
- $0 \leq A_i \leq 9$
- $\max(A_1, A_2, \dots, A_N) \neq 0$
- $0 \leq R_{i,j} \leq 9$
- $\max(R_{i,1},R_{i,2},\dots,R_{i,N}) \neq 0$
- If $i \neq j$, then $(R_{i,1},R_{i,2},\dots,R_{i,N}) \neq (R_{j,1},R_{j,2},\dots,R_{j,N})$
- All input values are integers
Input
$N$ $K$ $T$
$A_1$ $A_2$ $\dots$ $A_N$
$R_{1,1}$ $R_{1,2}$ $\dots$ $R_{1,N}$
$R_{2,1}$ $R_{2,2}$ $\dots$ $R_{2,N}$
$\vdots$
$R_{K,1}$ $R_{K,2}$ $\dots$ $R_{K,N}$
Output
Output the probability that Alice succeeds in unlocking the lock, computed $\text{mod }120586241$, followed by a newline.
Sample
Sample 1
Input
2 3 2 1 2 1 2 3 4 8 8
Output
26796943
The probability that Alice succeeds in unlocking the lock is $\frac{5}{9}$.
Sample 2
Input
4 1 2 2 4 6 8 1 2 3 4
Output
1
The probability that Alice succeeds in unlocking the lock is $1$.
Sample 3
Input
5 10 1000000000 5 9 3 0 4 8 7 5 4 0 5 7 7 8 4 5 6 3 6 1 7 1 5 6 2 7 5 4 0 8 7 9 0 1 5 6 8 3 5 3 0 2 4 6 4 6 4 6 3 2 7 1 4 5 4
Output
78122554
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。