問題一覧 > 通常問題

No.3415 Dial Lock

レベル : / AI推定難易度 : 3000 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : NyaanNyaan / テスター : risujiroh
お気に入りにしたユーザー ProblemId : 12915 / 自分の提出
問題文最終更新日: 2025-12-22 00:36:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2025 (順位表) の他の問題:

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.
Note that Alice does not turn the dials or pull the shackle other than during an operation.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。