题意
给定一个长度为 \(n\) 的数字串 \(s\) 和只包含 yo 的字符串 \(t\)，yoimiya 会和 oimiya 玩 \(n\) 轮游戏，初始有一个数字串 \(x\) 为 \(0\)，每次：
- 如果 \(t_i\) 是
y则是 yoimiya 操作，如果是o则是 oimiya 操作。 - 每次操作：将 \(s_i\) 或者 \(0\) 加入 \(x\) 的末尾。
如果最后 \(x\) 是 \(11\) 的倍数，那么 yoimiya 获胜，否则 oimiya 获胜。
假设两人都是绝顶聪明的，那么最后谁会获胜？
Sol
简单博弈论，考虑博弈 dp。
\(f_{ij}\) 表示第 \(i\) 次操作，当前 \(x mod 11 = j\) 是否获胜。
转移显然是 trivial 的，\(O(n)\)。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <ctime>
#define int long long
using namespace std;
/* #ifdef ONLINE_JUDGE */
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
/* #endif */
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
string read_() {
string ans;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9') {
ans += c;
c = getchar();
}
return ans;
}
string read__() {
string ans;
char c = getchar();
while (c < 'a' || c > 'z')
c = getchar();
while (c >= 'a' && c <= 'z') {
ans += c;
c = getchar();
}
return ans;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 1e6 + 5;
array <int, N> isl;
array <array <int, 12>, N> f;
string s1, s2;
bool dfs(int step, int sum, int n) {
if (~f[step][sum]) return f[step][sum];
if (step == n) {
if (!sum) return true;
else return false;
}
bool tp1 = dfs(step + 1, (sum + isl[step + 1]) % 11, n),
tp2 = dfs(step + 1, sum, n);
if (s2[step + 1] == 'y')
return f[step][sum] = (tp1 || tp2);
else
return f[step][sum] = (tp1 && tp2);
}
signed main() {
freopen("yo.in", "r", stdin);
freopen("yo.out", "w", stdout);
int n = read();
s1 = " " + read_(), s2 = " " + read__();
array <int, 12> tp;
tp.fill(-1);
f.fill(tp);
int idx = 1;
for (int i = n; i; i--) {
isl[i] = (s1[i] - '0') * idx % 11;
idx = idx * 10 % 11;
}
if (dfs(0, 0, n))
puts("yoimiya");
else
puts("oimiya");
return 0;
}