其實(shí)我們發(fā)現(xiàn)很多博弈論的動(dòng)態(tài)規(guī)劃都是從后往前的，比如過(guò)河卒和本題。

這是因?yàn)閺哪撤N角度上來(lái)說(shuō)這些動(dòng)態(tài)規(guī)劃有后效性而無(wú)前效性。

所以設(shè)計(jì)狀態(tài) \(dp_{i,j}\) 表示第 \(i\) 次操作 \(T\) 模 \(7\) 的余數(shù)為 \(j\) 的情況下能否走到 Takahashi 的勝利狀態(tài)。

然后就是正常的博弈論倒序轉(zhuǎn)移。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e5+114;
string X,S;
int n;
int dp[maxn][10];//第 i 次操作后 base-10 T % 7 = j 是否可能達(dá)成目標(biāo) 
signed main(){
	cin>>n;
	cin>>X>>S;
	dp[n][0]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=0;j<7;j++){
			if(S[i]=='T'){
				dp[i][j]=dp[i+1][(j*10+((int)(X[i]-'0')%7))%7]|dp[i+1][(j*10)%7];
			}
			else{
				dp[i][j]=dp[i+1][(j*10+((int)(X[i]-'0')%7))%7]&dp[i+1][(j*10)%7];
			}
		}
	}
	cout<<(dp[0][0]==1?"Takahashi":"Aoki");
}