Loading... ## 题意 每次操作时取 $n$ 对整数中的一对 $(l,r)$(需要满足 $r-l>2$),将其变成 $(l+\frac{r-l}{3},l+\frac{r-l}{3}×2)$ 或是 $(l,r-\frac{r-l}{3})$,所有除法都是向下取整。当一个玩家没法操作时就输了。 构造 $n$ 对整数使得先手必胜,给定一个 $p$ 使得 $l,r$ 均小于等于 $p$。 $n\leq 1000,p\leq 10^9$ ## 题解 大家都是打表做的,但是没人说怎么打表。 首先肯定是要算出 sg 值的,然后发现 $sg$ 值只和 $r-l$ 有关,令 $x=r-l$ 则两种操作分别是把 $x$ 变成 $\lfloor\frac{x}{3}\rfloor,x-\lfloor\frac{x}{3}\rfloor$,先随便打个表,猜测最终 sg 是一段一段的,并且段数很少。于是换个打表方式记 $pos_i$ 表示第 $i$ 段结束位置,$sg_i$ 表示第 $i$ 段的 sg 值。由于对于一个 $x$ 会有一段取值的 $y$ 使得 $\lfloor\frac{y}{3}\rfloor=x$ 同样有一段取值的 $y$ 使得 $y-\lfloor\frac{y}{3}\rfloor=x$。那么用两个 $u,v$ 表示当前考虑一段 $x$ 的取值使 $\lfloor\frac{x}{3}\rfloor=pos_u,x-\lfloor\frac{x}{3}\rfloor=pos_v$,算出最大的 $x$ 满足条件,并作为新的一段 sg 值加入数组,然后挪动成为上界指针即可。同样也可以以此证明,sg 值段数只有 $\mathcal{O}\left(\log V\right)$ 级别。 剩下的随便 dp 一下就可以了。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE int #define OUTPUT_DATA_TYPE int inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} const long long mod=1000000007; int pos[1000],sg[1000]; long long cntSg[4],f[1010][4],p; long long getSum(long long l,long long r){ l=p-l,r=p-r; return (l+r)*(l-r+1)/2%mod; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif register int i,j,k,cnt=0,u=1,v=1,n; register long long uMax,vMax; n=read();p=read(); pos[++cnt]=2; while(pos[cnt]<p){ uMax=pos[u]*3+2; if(pos[v]&1) vMax=(pos[v]-1)/2*3+1; else vMax=pos[v]/2*3; for(i=0;i<2;++i) if(sg[u]!=i&&sg[v]!=i) break; if(i!=sg[cnt]) sg[++cnt]=i; pos[cnt]=std::min(uMax,vMax); if(uMax==pos[cnt]) ++u; if(vMax==pos[cnt]) ++v; } for(i=1;i<=cnt;++i) (cntSg[sg[i]]+=getSum(pos[i-1]+1,std::min(pos[i],(int)p)))%=mod; f[0][0]=1; for(i=1;i<=n;++i) for(j=0;j<4;++j) for(k=0;k<4;++k) (f[i][j^k]+=cntSg[j]*f[i-1][k])%=mod; print((f[n][1]+f[n][2]+f[n][3])%mod); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改:2024 年 04 月 02 日 © 允许规范转载 打赏 赞赏作者 赞 1 如果觉得我的文章对你有用,请随意赞赏