Focusing only on Aoki’s and Snuke’s strategies, there are four possible scenarios for the \(i\)-th round, as follows.

1. Takahashi can become the only winner by playing paper. (The other two both play rock.)
2. Takahashi can become the only winner by playing rock. (The other two both play scissors.)
3. Takahashi can become the only winner by playing scissors. (The other two both play paper.)
4. Takahashi cannot become the only winner by playing any hand. (The other two play different hands.)

Let the opponents’ strategy be the sequence \((v_1,\dots,v_t)\), representing each of the \(k\) rounds as one of the four above.

Find the probability distribution for the opponents’ strategy in \(O(k4^k)\).

Let us find a way to find the probability distribution representing what the opponents’ strategy becomes among the \(4^k\) possible ones.

An obvious policy is to try all \(nm\) choices, but it takes \(O(k9^k)\) time, so let us do convolution using DP similar to the fast zeta transform.

Policy

Let \(A_{v_1,\dots,v_k}\) be the probability that Aoki satisfies the following conditions, where \(v_i=1,2,3\).

• If \(v_i=1\), he plays rock in the \(i\)-th round.
• If \(v_i=2\), he plays scissors in the \(i\)-th round.
• If \(v_i=3\), he plays paper in the \(i\)-th round.

Let \(A'_{v_1,\dots,v_k}\) be the probability that Aoki satisfies the following conditions, where \(v_i=1,2,3,4\).

• If \(v_i=1\), he plays rock in the \(i\)-th round.
• If \(v_i=2\), he plays scissors in the \(i\)-th round.
• If \(v_i=3\), he plays paper in the \(i\)-th round.
• If \(v_i=4\), he may play anything.

Let \(f\) be the process that finds \(\{A'_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\) from \(\{A_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\).

For Snuke, we similarly define \(B_{v_1,\dots,v_k}\) and \(B'_{v_1,\dots,v_k}\). Then, \(C'_{v_1,\dots,v_k}:=A'_{v_1,\dots,v_k}B'_{v_1,\dots,v_k}\) will be the probability that the following is satisfied.

• If \(v_i=1\), both play rock in the \(i\)-th round.
• If \(v_i=2\), both play scissors in the \(i\)-th round.
• If \(v_i=3\), both play paper in the \(i\)-th round.
• If \(v_i=4\), they may play anything.

Therefore, if \(C_{v_1,\dots,v_k}\) is the sequence that satisfies \(\{C'_{v_1,\dots,v_k}\}_{v_i=1,2,3,4} = f(\{C_{v_1,\dots,v_k}\}_{v_i=1,2,3,4})\), \(C_{v_1,\dots,v_k}\) is the probability distribution that we seek.

Implementation

\(\{A_{v_1,\dots,v_k}\}_{v_1,\dots,v_n=1,2,3,4}\) can be directly found from input.

\(f\) can be computed by adding each term \(A_{v_1,\dots,v_k}\) such that \(v_i\neq 4\) to \(A_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\), similarly to the fast zeta transform. That is, we let \(A^0_{v_1,\dots,v_k}:=A_{v_1,\dots,v_k}\), compute \(A^{i+1}_{v_1,\dots,v_k}\) for each \(i\) as follows, and then let \(A'_{v_1,\dots,v_k}:=A^k_{v_1,\dots,v_k}\). (Here, superscripts are indices, not powers.)

• \(A^{i+1}_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}\)
• \(A^{i+1}_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k} := A^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+A^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)

Here, \(A^j_{v_1,\dots,v_k}\) is the probability that the following is satisfied.

• For each \(i\) such that \(i<j\):
  • If \(v_i=1\), play rock in the \(i\)-th round.
  • If \(v_i=2\), play scissors in the \(i\)-th round.
  • If \(v_i=3\), play paper in the \(i\)-th round.
  • If \(v_i=4\), play anything.
• For each \(i\) such that \(i\ge j\):
  • If \(v_i=1\), play rock in the \(i\)-th round.
  • If \(v_i=2\), play scissors in the \(i\)-th round;
  • If \(v_i=3\), play paper in the \(i\)-th round.
  • (If \(v_i=4\), playing anything is unacceptable.)

We do the same for the inverse function. That is, for each \(i\), we subtract each term \(A'_{v_1,\dots,v_k}\) such that \(v_i\neq 4\) from \(A'_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\).

Find the answer from the probability distribution of the opponents’ strategy in \(O(k4^k)\)

From the probability distribution we have just found, let us next find the probability that Takahashi gets unhappy for each strategy for Takahashi. Here, we can use a term-by-term conversion similar to the above.

Let \(D_{v_1,\dots,v_k}\) be the probability that the following conditions are satisfied, where \(v_i=1,2,3,4\).

• If \(v_i=1\), anything other than both players playing rock is allowed in the \(i\)-th round.
• If \(v_i=2\), anything other than both players playing scissors is allowed in the \(i\)-th round.
• If \(v_i=3\), anything other than both players playing paper is allowed in the \(i\)-th round.
• If \(v_i=4\), playing anything is allowed.

To find \(D_{v_1,\dots,v_k}\) from \(C_{v_1,\dots,v_k}\), we let \(C_{v_1,\dots,v_k}^0:=C_{v_1,\dots,v_k}\), compute \(C^{i+1}_{v_1,\dots,v_k}\) for each \(i\) as follows, and then let \(D_{v_1,\dots,v_k}:=C^k_{v_1,\dots,v_k}\).

• \(C^{i+1}_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)
• \(C^{i+1}_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}:=C^i_{v_1,\dots,v_{i-1},1,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},2,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},3,v_{i+1}\dots v_k}+C^i_{v_1,\dots,v_{i-1},4,v_{i+1}\dots v_k}\)

Now that we have found the probability \(D_{v_1,\dots,v_k}\) that Takahashi gets unhappy, the answer is \(1-D_{v_1,\dots,v_k}\).

Sample Implementation in C++