P4459 题解
Delov
·
·
题解
可以发现，每次是在根据“不知道”来排除决策集合中的某些东西，例如：
第一轮 A 说不知道，那么积拆分不唯一。
第二轮 B 说不知道，那么说明和对于所有和拆分 (a,b)，a \times b 的和拆分不唯一的 (a,b) 不唯一。
第三轮 A 又说不知道，那么对于所有的积拆分 (a,b)，a+b 的所有积拆分中，其和拆分不唯一的的积拆分不唯一的 (a,b) 不唯一。
我们发现每次说不知道，就是在嵌套上一个"和/积拆分...不唯一"，那么可以尝试递归解决问题。
函数 \operatorname {DfsA}(dep,vec) 表示之前一共说过 dep 次不知道，剩余决策集合为 vec，此时轮到 A 判断，返回 A 此时的决策集合。
考虑如何排除，就是枚举剩余决策集合的每个元素 $(a,b)$，将其和/积算出并作和/积拆分，考虑满足要求的拆分是否唯一，若不唯一则其仍是一个合法决策，否则排除之。是否满足要求则是一个递归问题，递归边界即为之前没有说过“不知道”，此时判断条件就是和/积拆分方案数。
我们通过这样的处理可以找出前 $t$ 次两人都说不知道之后两人各自的剩余决策集合，现在我们需要看他们是否“知道”了。
判断方法相同，我们就枚举所有决策，看是否存在唯一一个满足要求的，判断是否满足的处理要求同上，递归处理即可。发现递归过程中，除了第一层决策集合可能是特殊的，往下递归后每层的决策集合实际上就是某个数的和/积拆分的所有方案，于是我们可以对这些过程记忆化。
跑的甚至比提交答案快？应该是所有提交代码里最快的。
### code
```cpp
#include <bits/stdc++.h>
typedef long long ll;typedef unsigned long long ull; typedef double db;typedef long double ldb;
#define fre(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)
#define Rep(i,a,b) for(int i=a;i<=b;++i)
#define Dwn(i,a,b) for(int i=a;i>=b;--i)
#define pii pair<int,int>
#define mair make_pair
#define fir first
#define sec second
using namespace std;
int Lim,Ned;
string str;
unordered_map<int,int>MapB,MapC;
int ExpandB(int x){
if(MapB.count(x))return MapB[x];
int res=0;for(int i=Lim;x-i>=i;++i)++res;
return MapB[x]=res;
}
int ExpandC(int x){
if(MapC.count(x))return MapC[x];
int res=0;for(int i=Lim;x/i>=i;++i)if(x%i==0)++res;
return MapC[x]=res;
}
vector<pii> DfsA(int ,const vector<pii>&);
vector<pii> DfsB(int ,const vector<pii>&);
vector<pii>ExA(int x){ vector<pii>res;for(int i=Lim;i*i<=x;++i)if(x%i==0)res.emplace_back(i,x/i);return res; }
vector<pii>ExB(int x){ vector<pii>res;for(int i=Lim;i+i<=x;++i)res.emplace_back(i,x-i);return res; }
unordered_map<int,int>MapAx[20],MapBx[20];
int CfsA(int,int);
int CfsB(int,int);
int CfsA(int dep,int x){
if(dep==0)return ExpandC(x);
if(MapAx[dep].count(x))return MapAx[dep][x];
vector<pii>vec=ExA(x);int res=0;
for(auto it : vec)res+=(CfsB(dep-1,it.fir+it.sec)>1);
return MapAx[dep][x]=res;
}
int CfsB(int dep,int x){
if(dep==0)return ExpandB(x);
if(MapBx[dep].count(x))return MapBx[dep][x];
vector<pii>vec=ExB(x);int res=0;
for(auto it : vec)res+=(CfsA(dep-1,it.fir*it.sec)>1);
return MapBx[dep][x]=res;
}
vector<pii> DfsA(int dep,const vector<pii> & vec){
if(dep==0)return vec;
vector<pii>res;
for(auto it : vec)if(CfsB(dep-1,it.fir+it.sec)>1)res.emplace_back(it);
/*for(auto it : vec){
vector<pii> tmp=DfsB(dep-1,ExB(it.fir+it.sec));
if(tmp.size()>1)res.emplace_back(it);
}*/
return res;
}
vector<pii> DfsB(int dep,const vector<pii> & vec){
if(dep==0)return vec;
vector<pii>res;
for(auto it : vec)if(CfsA(dep-1,it.fir*it.sec)>1)res.emplace_back(it);
/*for(auto it : vec){
vector<pii> tmp=DfsA(dep-1,ExA(it.fir*it.sec));
if(tmp.size()>1)res.emplace_back(it);
}*/
return res;
}
int Get(int n,int m){
vector<pii>vecA=ExA(n*m),vecB=ExB(n+m);
if(n==78 && m==108){ cerr<<"\n"; }
if(str=="Alice"){
Rep(i,1,Ned){
if((i&1)){ vecA=DfsA(i-1,vecA);if(vecA.size()<=1)return 0; }
else{ vecB=DfsB(i-1,vecB);if(vecB.size()<=1)return 0; }
}
if(!(Ned&1)){
vecA=DfsA(Ned,vecA);int res=0;
for(auto it : vecB){
if(DfsA(Ned,ExA(it.fir*it.sec)).size()==1)++res;
}
if(vecA.size()==1 && res==1)return Ned;
else return 0;
}else{
vecB=DfsB(Ned,vecB);int res=0;
for(auto it : vecA){
if(DfsB(Ned,ExB(it.fir+it.sec)).size()==1)++res;
}
if(vecB.size()==1 && res==1)return Ned;
else return 0;
}
}
if(str=="Bob"){
Rep(i,1,Ned){
if((i&1)){ vecB=DfsB(i-1,vecB);if(vecB.size()<=1)return 0; }
else { vecA=DfsA(i-1,vecA);if(vecA.size()<=1)return 0; }
}
if(!(Ned&1)){
vecB=DfsB(Ned,vecB);int res=0;
for(auto it : vecA){
if(DfsB(Ned,ExB(it.fir+it.sec)).size()==1)++res;
}
if(vecB.size()==1 && res==1)return Ned;
else return 0;
}else{
vecA=DfsA(Ned,vecA);int res=0;
for(auto it : vecB){
if(DfsA(Ned,ExA(it.fir*it.sec)).size()==1)++res;
}
if(vecA.size()==1 && res==1)return Ned;
else return 0;
}
}
return 0;
}
void solve(){
cin>>Lim>>str>>Ned;
for(int s=Lim+Lim;;++s){
for(int i=Lim;s-i>=i;++i)
if(Get(i,s-i)==Ned)return cout<<i<<" "<<s-i<<"\n",void();
}
}
int main (){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);return solve(),0; }
```