E - Lucky 7 Battle Editorial by en_translator


Let us consider if Takahashi is possible to win after the \(N-1\) round. Let us regard \(T\) as a decimal number and \(r\) be the remainder by \(7\). Also, we identify \(S_N\) with the corresponding digit.

If \(X_N\) is T, then Takahashi will win if either \(10r\) or \(10r+S_N\) is a multiple of \(7\).
If \(X_N\) is A, then Takahashi will win if both \(10r\) and \(10r+S_N\) are multiples of \(7\).

As you can see, we can define the following DP, in the reversed order.

dp[i]=The set of integers \(r\) that satisfies the following condition:
Condition: if the remainder of \(T\) divided by \(7\) is \(r\) after the \(i\)-th round end, Takahashi will win

The initial state is \( dp[N]=\{0\}\). The transitions are
if \(X_i\) is T, \(dp[i-1]=\{ r \mid (10r \bmod 7) \in dp[i] \ \text{ or }\ (10r+S_i \bmod 7) \in dp[i]\}\), and
if \(X_i\) is A, \(dp[i-1]=\{ r \mid (10r \bmod 7) \in dp[i]\ \text{ and }\ (10r+S_i \bmod 7) \in dp[i]\}\).

If \(0 \in dp[0]\) at last, Takahashi wins; otherwise, Aoki wins. The time complexity is \(O(N)\).

posted:
last update: