F1 蒲公英的约定（vol.1） 题解

· · 题解

显然是 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;
}