算法

(博弈型dp) $O(n)$

• 不论采取什么程序，赢与否取决于数字是否为7的倍数。
• 这意味着无论进行什么过程，游戏状态都可以用该数字除以 $7$ 的余数表示。
• 当确认操作直到第 $i$ 轮时，通过将到目前为止确认的数除以 $7$ 得到的余数为 $r$。
• 在这种状态下，先前的操作是哪种操作不会影响以后的操作。
• 换句话说，所有状态可以被限制为 $(i, r)$ 的组，即 $210^57$ 种方式。
• 回溯是一种技术，它允许你在确定某个状态的转换目标的所有胜利或失败的情况下做出对自己有利的选择，从而决定某个状态的胜利或失败。
• 我认为这就像回溯，因为胜利或失败是在与最终状态相反的方向上决定的。
• 这题的最终状态为 $(N, 0)$ 至 $(N, 6)$。
• dp[i][r] := 在确认了第 $i$ 次运算之后，将确认当前的数 $T$ 除以 $7$ 的余数为 $r$ 是否为 “高桥先生获胜”的状态
• 若添加 $s_i$ 时，$dp[i][r] = dp[i + 1][(r + s_i ) \% 7]$
• 若添加 $0$ 时，$dp[i][r] = dp[i + 1][r]$

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::string;
using std::vector;

int main() {
    int n;
    string s, x;
    cin >> n >> s >> x;

    vector<int> dp(7);
    dp[0] = 1; // Takashi win
    int ten = 1;
    for (int i = n - 1; i >= 0; --i) {
        vector<int> old(7);
        swap(dp, old);
        rep(j, 7) {
            int nj = (j + ten * (s[i] - '0')) % 7;
            if (x[i] == 'T') {
                dp[j] = old[j] | old[nj];
            }
            else {
                dp[j] = old[j] & old[nj];
            }
        }

        ten = (ten * 10) % 7;
    }

    if (dp[0] == 1) cout << "Takahashi\n";
    else cout << "Aoki\n";

    return 0;
}