题目概述

你要跟一共 $m$ 个人玩剪刀石头布的游戏，其中 R(Rock) 胜 S(Scissors)、S(Scissors) 胜
P(Paper)、P(Paper) 胜 R(Rock)。如果出同样的算平局。你与一个人共玩 $n$ 局，胜的
局数多的人胜出，如果胜的局数相同就打成平手。
你现在知道了这 $m$ 个人在每局分别会出什么，你想要确定一个出拳的序列，使得在与
这 $m$ 个人的游戏中都能打成平手。输出满足条件的序列数。

解题报告

$3^{n}m$ 会炸掉，然后我们就会发现折半搜索就行了……效率 $O(3^{n\over 2}m)$ 。

示例程序

#include<map>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=20,maxm=100;
const int fl[3][3]={{0,-1,1},{1,0,-1},{-1,1,0}};//0 R|1 P|2 S

class EllysRPS{
    vector<string> a;int n,m;LL ans;int ID[256];
    vector<int> now;map<vector<int>,int> ha;
    void Dfs(int L,int R,int f){
        if (L>R) {f>0?ha[now]++:ans+=(LL)ha[now];return;}
        for (int i=0;i<3;i++){
            for (int j=0;j<m;j++) now[j]+=f*fl[i][ID[(int)a[j][L]]];
            Dfs(L+1,R,f);
            for (int j=0;j<m;j++) now[j]-=f*fl[i][ID[(int)a[j][L]]];
        }
    }
public:
    LL getCount(vector<string> s){
        a=s;m=a.size();n=a[0].length();ID[(int)'R']=0;ID[(int)'P']=1;ID[(int)'S']=2;
        ans=0;now.resize(m);Dfs(0,n/2-1,1);Dfs(n/2,n-1,-1);return ans;
    }
};