AT_abc195_e 题解

思路

这道题需要倒序计算。

定义 $dp_{i,j}=f$ 表示第 $i$ 轮结束后余数为 $j$ ，$f=1$ 时， Takahashi 必胜，否则 Aoki 必胜。

动态转移方程式

令：

$x=dp_{i,(j \times 10 + a_i)\bmod 7}$

$y=dp_{i,j \times 10 \bmod 7}$

$dp_{i-1,j}=\begin{cases}x\ \operatorname{or}\ y&b_i=T\x\ \operatorname{and}\ y&b_i=A\end{cases}$

$x$ 为选 $a_i$ 的余数, $y$ 为不选 $a_i$ 的余数。

如果当前是 Takahashi 选，那只要两个中有一个能让 Takahashi 必胜就行。

如果当前是 Aoki 选，那需要两个都能让 Takahashi 必胜才能使 Takahashi 必胜，否则当前情况 Aoki 必胜。

代码

#include <bits/stdc++.h>
using namespace std;
long long n,dp[200010][10];
string a,b;
int main(){
	cin>>n;
	cin>>a>>b; 
	a=" "+a;
	b=" "+b;
	memset(dp,0,sizeof dp);
	dp[n][0]=1;
	for(int i=n;i>=1;i--)
		for(int j=0;j<7;j++){
			bool x=dp[i][(j*10+a[i]-'0')%7];
			bool y=dp[i][j*10%7];
			if(b[i]=='T')
				dp[i-1][j]=x|y;
			else
				dp[i-1][j]=x&y;
		}
	cout<<(dp[0][0]==0?"Aoki":"Takahashi")<<endl;
	return 0;
}