“科大讯飞杯”第十七届同济大学程序设计预选赛暨高校网络友谊赛G硬币游戏ⅢSG函数/MutliSG游戏终于补完了……

这题是Mutli-SG 的变形。

本质还是SG函数。

不考虑算法复杂度来看&＃xff1a;

每个局面的SG值等于只有一个硬币的SG值的异或和。

我们这样想&＃xff1a;把长度为n的字符串当成n堆石子。

从左往右第i位为1表示第i堆有i个石子。

一次操作相当于把第x堆石子分成  若干堆&＃xff08;小于第x堆大小&＃xff09;。&＃xff08;会出现某一位有2个正面朝上的硬币&＃xff0c;即2个堆大小相同的堆&＃xff0c;但是他们SG的异或和为0&＃xff0c;相当于消去他们&＃xff0c;即变成背面朝上&＃xff09;

有了上面的转化&＃xff0c;我们就能用SG函数求解了。

暴力打出SG函数的表是n*n*k的复杂度。

正常人的做法&＃xff1a;打表发现&＃xff0c;SG[i]&＃61;min(lowbit(i),2^w);  2^w<&＃61;k<2^(w&＃43;1)

然后O1打出SG&＃xff0c;直接搞即可。

下面程序附带打表

#include
using namespace std;
typedef long long ll;
#define ls (o<<1)
#define rs (o<<1|1)
#define pb push_back
const double PI&＃61; acos(-1.0);
const int M &＃61; 1e&＃43;7;
/*
int head[M],cnt;
void init(){cnt&＃61;0,memset(head,0,sizeof(head));}
struct EDGE{int to,nxt,val;}ee[M*2];
void add(int x,int y){ee[&＃43;&＃43;cnt].nxt&＃61;head[x],ee[cnt].to&＃61;y,head[x]&＃61;cnt;}
*/
int SG[M];
int vs[M];
char s[M];
int main()
{ios::sync_with_stdio(false);cin.tie(0);int n,k;cin>>n>>k;
// SG[1]&＃61;1;//只有一个SG&＃61;&＃61;0的可达
// for(int i&＃61;2;i<&＃61;100;i&＃43;&＃43;)
// {
// memset(vs,0,sizeof(vs));
// vs[0]&＃61;1;//翻一枚硬币
// for(int j&＃61;2;j<&＃61;k;j&＃43;&＃43;)//翻几枚硬币
// {
// if(i-j&＃43;1<1)break;
// int tp&＃61;0;
// for(int q&＃61;i-j&＃43;1;q// vs[tp]&＃61;1;
// }
// for(int j&＃61;1;j<&＃61;100;j&＃43;&＃43;)if(!vs[j]){
// SG[i]&＃61;j;
// break;
// }
// }
// for(int i&＃61;1;i<&＃61;100;i&＃43;&＃43;)
// {
// cout<// }int ans&＃61;1;while(k>1){k/&＃61;2;ans*&＃61;2;}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)SG[i]&＃61;min(-i&i,ans);cin>>s;int tp&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(s[i-1]&＃61;&＃61;&＃39;1&＃39;)tp^&＃61;SG[i];}if(tp&＃61;&＃61;0)cout<<"No"<}

下面是题解的证明&＃xff1a;&＃xff08;大佬的做法。。。&＃xff09;