F2 蒲公英的约定（vol.2） 题解

· · 题解

显然是 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，有

\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，有

\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。

而

&\ \ \ \ \ \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;
}