ABC195 - E Lucky 7 Battle

atcoder.jp
ゲーム系。
勝負が確定している後ろからDPする(バックトラックというらしい)
この方針は正しかったが、7の倍数判定を無駄に考えすぎて解けず。

【問題】
数列が与えられる。
文字列の手番に従って、高橋君と青木君は新しい数列の末尾にS[i]か0を加える。
最終的に出来た数列が7の倍数なら高橋君の勝ち。
お互い最適に動いたとき、高橋君はゲームに勝てるか？
【典型ポイント】
バックトラック
10の階乗のmodを前計算する
倍数系の問題は都度modを取りながら進められる
【方針】
以下のようなDPテーブルを作る
dp[i][mo]:= i手目まで進んだ時の、余りがmoである場合に高橋君が勝てるかどうか
メモ化でDPする方法が分からなかったので他の人のコードを真似した。書けるようになると楽かもしれない

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int p[201010]; //10の階乗 mod 7
bool memo[201010][7], seen[201010][7];
int main(){
    int N; string S, X; cin >> N >> S >>X;

    p[0] = 1; rept(i, 1, 201010)p[i]= (p[i-1] * 10) % 7;

    //メモ化再帰
    //func(i, mo):=i回目の操作が確定していて、確定している数字を7で割った余りがmoのとき、高橋君の勝ち状態であるか
    auto func = [&](auto&& self, int i, int mo) -> bool{
        if(i==N)return mo == 0;

        if(seen[i][mo])return memo[i][mo];
        seen[i][mo] = true;

        if(X[i] == 'T'){
            //add S[i]
            if(self(self, i+1, (mo + (S[i] - '0') * p[N-i-1]) % 7)) return memo[i][mo] = true;
            //add 0
            if(self(self, i+1, mo))return memo[i][mo] = true;

            return memo[i][mo] = false;
        }
        else{
            //add S[i]
            if(!self(self, i+1, (mo + (S[i] - '0') * p[N-i-1]) % 7)) return memo[i][mo] = false;
            //add 0
            if(!self(self, i+1, mo))return memo[i][mo] = false;

            return memo[i][mo] = true;
        }
    };
    cout << (func(func, 0, 0) ? "Takahashi" : "Aoki") << ln;
}