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: