D - The Simple Game
k<=10, 记忆化搜索,状态数2e5*20
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f#define int long longconst int N = 200010;
vector<int> G[N];
bool a[N][30];
bool vis[N][30];
string s; int mk;int dfs(int u, int step){if(vis[u][step]){return !a[u][step];}vis[u][step] = 1; if(step == 2*mk + 1){if(s[u] == 'A') a[u][step] = 1;else a[u][step] = 0;return !a[u][step];}a[u][step] = 0;for(auto v:G[u]){a[u][step] |= dfs(v, step + 1);}//cout << (!a[u][step]) << '\n';return !a[u][step];
}
void solve(){int n, m; cin >> n >> m >> mk;for(int i = 1; i <= n; i ++ ) {for(int j = 1; j <= 2 * mk + 1; j ++) vis[i][j] = 0;G[i].clear();}
cin >> s; s = "a" + s;while(m -- ){int u, v; cin >> u >> v; G[u].pb(v);
}if(dfs(1, 1)){cout << "Bob\n";
}
else cout << "Alice\n";}signed main(){std::ios::sync_with_stdio(false);int T = 1; cin >> T;while(T--){solve();}
}
E - Wind Cleaning
F - Not Adjacent
折半搜索，双搜
从n/2处断开，前面搜的存在mp里，3* 215log(215)
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define pii pair<int,int>
#define ll long long
#define pb push_back
#define ft first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f//#define int long longint a[100];
unordered_map<int, ll> mp0;
unordered_map<int, ll> mp1;
int n, m;ll ans;
void dfs1(int step, int cur, int lst){if(step >= n/2) {if(lst)mp1[cur] ++;else mp0[cur] ++;return ;}if(!lst)dfs1(step + 1, (1ll*cur + 1ll*a[step]) % m, 1);dfs1(step + 1, cur, 0);
}void dfs2(int step, int cur, int lst){if(step >= n + 1){ans += mp0[(m - cur) % m];return ;}if(!lst) dfs2(step + 1, (1ll*cur + 1ll*a[step]) % m, 1);dfs2(step + 1, cur, 0);
}
void dfs3(int step, int cur, int lst){if(step >= n + 1){ans += mp0[(m - cur) % m] + mp1[(m - cur) % m];return ;}if(!lst) dfs3(step + 1, (1ll*cur + 1ll*a[step]) % m, 1);dfs3(step + 1, cur, 0);
}
void solve(){cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];if(n == 1){if(a[1] % m ==0)cout << 2 << '\n';else cout << 1 << '\n';return ;}dfs1(1, 0, 0);dfs2(n/2 + 1, a[n/2], 1);dfs3(n/2 + 1, 0, 0);cout << ans << '\n';
}signed main(){std::ios::sync_with_stdio(false);int T = 1; //cin >> T;while(T--){solve();}
}