自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 22:30:22，当前版本为作者最后更新于2021-03-23 13:49:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然是 SG 函数题。

如果不会 SG 函数可以学一下，推销我的博客。

题外话：本来想直接出先手是否必胜的，后来懒得构造后手必胜数据就整成现在这样脚造数据都骗不到分的问法（

有一说一，这题的 SG 函数还是很好求的，不用找什么规律，证明更是非常简单。

回到题解。

首先我们考虑一串数列 $(a_1,a_2,\dots,a_n,0)$ 的 SG 值。

显然 $(0)$ 的 SG 值为 $0$。现在考虑 $(a_2,\dots,a_n,0)$ 的 SG 值已知且为 $t$。

显然 $(a_1,a_2,\dots,a_n,0)$ 的后继状态有 $(a_1-1,a_2,\dots,a_n,0),(a_1-2,a_2,\dots,a_n,0),\dots,(a_2,\dots,a_n,0)$。由此可以发现 $(a_1,a_2,\dots,a_n,0)$ 的 SG 函数值在 $a_1 \le t$ 时为 $a_1-1$，在 $a_1 > t$ 时为 $a_1$。

再看原题中 $x$ 的 SG 函数。显然 $t_1=\lfloor\sigma x\rfloor\ge\lfloor\sigma(x-t_1)\rfloor=t_2$，所以只有 $t_1=t_2$ 且 $x-\lfloor\sigma x\rfloor$ 的 SG 函数值为 $t_2$ 时 $x$ 的 SG 函数值才为 $t_1-1$，其余情况均为 $t_1$。这样就可以 $O(1)$ 求出 $x$ 的 SG 值了。

显然有 $x$ 及其后继状态 SG 值取遍 $0,1,\dots,\lfloor\sigma x\rfloor$ 且互不重复。因此只要对于最终整个游戏的 SG 值 $ans$ 满足 $\operatorname{SG}(x) \operatorname{xor} ans \le \lfloor\sigma x\rfloor$ 则将答案加上 $\dfrac{1}{n\lfloor\sigma x\rfloor}$。

时间复杂度 $O(n\log{n})$。

Code:

#include<cstdio>
#define rg register
#define LL __int128
#define ll unsigned long long
#define _tau(x) ((ll)((id<4)?(x*tau[id]):((x*q-1)/p)))
#define _sigma(x) ((ll)((id<4)?(x*sigma[id]):(x*p/q)))
const ll ntf=20190816170251;
inline char rc()
{
	static char buf[1048576],*pn=buf,*pe=buf;
	return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,1048576,stdin),pn==pe)?EOF:*pn++;
}
inline int read()
{
	int x=0;
	char cc=rc();
	while(cc<'0'||cc>'9')cc=rc();
	while(cc>='0'&&cc<='9')x=x*10+cc-'0',cc=rc();
	return x;
}
inline ll _read()
{
	ll x=0;
	char cc=rc();
	while(cc<'0'||cc>'9')cc=rc();
	while(cc>='0'&&cc<='9')x=x*10+cc-'0',cc=rc();
	return x;
}
void print(LL x)
{
	if(x>9)print(x/10);
	putchar(x%10^48);
}
int id,n,m;
ll s[300007],d,p,q,r,SG[300007];
double tau[7]={0,1.242640687119285,1.8301270189222,1.61803398874989};
double sigma[7]={0,0.8047378541243,0.5464101615137,0.61803398874989};
inline ll _gcd(ll a,ll b)
{
	while(b^=a^=b^=a%=b);
	return a;
}
inline ll sg(ll x)
{
	ll t=_sigma(x);
	if(!t)return 0;
	return t-(((x-_tau(t)-1)/t)&1);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	LL d=exgcd(b,a%b,y,x);
	y-=a/b*x;return d;
}
inline LL _inv(LL a)
{
	LL d,x,y;
	d=exgcd(ntf,a,x,y);
	return (y%ntf+ntf)%ntf;
}
int main()
{
	id=rc()^48,n=read();
	for(rg int i=1;i<=n;++i)s[i]=_read();
	(id>=4)&&(p=_read(),q=_read(),d=_gcd(p,q),p/=d,q/=d);d=r=m=0;
	for(rg int i=1;i<=n;++i)SG[i]=sg(s[i]),d^=SG[i];
	for(rg int i=1;i<=n;++i)(_sigma(s[i])==0)?(++m):(((SG[i]^d)<=_sigma(s[i]))&&(r+=_inv(_sigma(s[i])),(r>=ntf)&&(r-=ntf)));
	print((d)?r*_inv(n-m)%ntf:0);
	return 0;
}