自动搬运

查看原文

来自洛谷，原作者为

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

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

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

以下是正文

---

显然是 SG 函数题。

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

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

回到题解。

SG 函数值规律：

令 $n=\left\lfloor\dfrac{x}{\tau+1}\right\rfloor$。若 $x=\lfloor n\tau \rfloor +n+1,n \in \mathbb{N}$，则 $\operatorname{SG}(x)=\operatorname{SG}(n)$；否则 $\operatorname{SG}(x)=x-n-1=\lfloor\sigma x\rfloor$。其中 $\tau=\dfrac{\sigma}{1-\sigma}$。

首先我们有一个引理：集合 $A=\{x|x=\lfloor n\tau \rfloor +n+1,n \in \mathbb{N}\}$，则 $\forall x \in \mathbb{Z_+}$，$\lfloor x\sigma \rfloor-\lfloor (x-1)\sigma \rfloor=[x \notin A]$。

引理证明：

（注：以下 $\{x\}$ 表示 $x-\lfloor x \rfloor$）

首先有 $\tau=\dfrac{\sigma}{1-\sigma}$，所以 $\sigma=\dfrac{\tau}{1+\tau}$。

接着，我们先证明 $\forall x \in A$，有 $\lfloor x\sigma \rfloor-\lfloor (x-1)\sigma \rfloor=0$。

对于 $x=\lfloor n\tau \rfloor +n$，有

$$\begin{aligned} \lfloor(\lfloor n\tau \rfloor +n)\sigma\rfloor&=\lfloor \lfloor n\tau \rfloor\sigma+n\sigma\rfloor\\ &=\lfloor n\tau\sigma-\{n\tau\}\sigma+n\sigma \rfloor\\ &=\lfloor n\sigma(\tau+1)-\{n\tau\}\sigma \rfloor\\ &=\lfloor n\tau-\{n\tau\}\sigma \rfloor\\ &=\lfloor \lfloor n\tau \rfloor+\{n\tau\}(1-\sigma) \rfloor=\lfloor n\tau \rfloor. \end{aligned}$$

对于 $x=\lfloor n\tau \rfloor +n+1$，有

$$\begin{aligned} \lfloor(\lfloor n\tau \rfloor +n+1)\sigma\rfloor&=\lfloor \lfloor n\tau \rfloor\sigma+n\sigma+\sigma\rfloor\\ &=\lfloor n\tau\sigma+(1-\{n\tau\})\sigma+n\sigma \rfloor\\ &=\lfloor n\sigma(\tau+1)+(1-\{n\tau\})\sigma \rfloor\\ &=\lfloor n\tau+(1-\{n\tau\})\sigma \rfloor\\ &=\lfloor \lfloor n\tau \rfloor+\{n\tau\}+(1-\{n\tau\})\sigma \rfloor\\ &=\lfloor \lfloor n\tau \rfloor+1-(1-\{n\tau\})(1-\sigma) \rfloor=\lfloor n\tau \rfloor. \end{aligned}$$

然后我们证明 $\forall x \notin A$，有 $\lfloor x\sigma \rfloor-\lfloor (x-1)\sigma \rfloor=1$。

由于 $\sigma<1$，显然有 $\lfloor x\sigma \rfloor-\lfloor (x-1)\sigma \rfloor \le 1$。

而

$$\begin{aligned} &\ \ \ \ \ \lfloor (\lfloor n\tau \rfloor+n)\sigma\rfloor-\lfloor [\lfloor(n-1)\tau\rfloor+(n-1)+1]\sigma \rfloor\\ &=\lfloor n\tau \rfloor-\lfloor(n-1)\tau\rfloor=(\lfloor n\tau \rfloor+n)-[\lfloor(n-1)\tau\rfloor+(n-1)+1], \end{aligned}$$

故只可能每个 $\lfloor x\sigma \rfloor-\lfloor (x-1)\sigma \rfloor=1$。

综上所述，证毕。

由引理，我们得到 $x$ 的后继状态为 $[x-\lfloor x\sigma \rfloor,x-1]$。所以当 $x \notin A$ 时，有 $x-\lfloor x\sigma \rfloor=(x-1)-\lfloor (x-1)\sigma \rfloor$，否则 $x-\lfloor x\sigma \rfloor=(x-1)-\lfloor (x-1)\sigma \rfloor+1$。

归纳可证规律成立。

显然有 $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 _mu(x) ((ll)((id<4)?(x*mu[id]):(x*(q-p)/q)))
#define _tau(x) ((ll)((id<4)?(x*tau[id]):(x*q/(q-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 mu[7]={0,0.1952621458756,0.4535898384862,0.3819660112501};
double tau[7]={0,5.1213203435596,2.2046349259880,2.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;
}
ll sg(ll x)
{
	if(!_sigma(x))return 0;
	ll y=_mu(x);
	ll t=_tau(y)+1;
	if(t==x)return sg(y);
	else return _sigma(x);
}
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;
}