$石子$石子

19 7 28

$最初想法$最初想法

以下 $N$N 表示 必胜态, $P$P 表示 必败态,
先考虑一堆石子, 手玩后发现奇数恒为 $P$P, 偶数恒为 $N$N,

小证明: 奇数为 $2n+1$2n+1, 由于 $奇\ast 奇=奇$奇∗奇=奇, 所以去掉其中一个因子后一定为偶数, 而偶数一定是能够取的, 因为最终状态 $1$1 为奇数 .

然后把 $M$M 堆石子搞成奇数个偶数即可 .

错的 .

$正解部分$正解部分

经过打表发现 $SG\left(x\right)=\max \{i\mid 2^i$SG(x)=max{i ∣ 2i| $x\}$x}, 即一个数字的 $SG$SG 值为这个数字的二进制表示中 $2^{末尾0的个数}-1$2末尾0的个数−1,
相当于 $SG\left(x\right)=lowbit\left(x\right)-1$SG(x)=lowbit(x)−1 .

可以初步了解到 $SG\left(奇数\right)=0$SG(奇数)=0,

题目转化为: 求出 $M$M 个 $SG$SG值 异或起来等于 $0$0 的方案数,

设 $sum\left[x\right]$sum[x] 表示 $SG$SG值 等于 $x$x 的石子数量 种类数, $x\in [1,logn]$x∈[1,logn],

$sum\left[0\right]=\lfloor \frac{n+1}{2}\rfloor$sum[0]=⌊2n+1​⌋
$sum\left[1\right]=\lfloor \frac{n-sum\left[0\right]+1}{2}\rfloor$sum[1]=⌊2n−sum[0]+1​⌋
$sum\left[2\right]=\lfloor \frac{n-sum\left[1\right]+1}{2}\rfloor$sum[2]=⌊2n−sum[1]+1​⌋
$...$              .              .              .
$sum\left[n\right]=\lfloor \frac{n-sum[n-1]+1}{2}\rfloor$sum[n]=⌊2n−sum[n−1]+1​⌋

当把一个数列的 二进制表示 全部去掉末尾只有 $1$1个 $0$0 的数字后,
再将其余数字的二进制末尾减去 $1$1 个 $0$0, 发现剩余的数字又会重新 连续 起来 .
依此得到上式 .

设 $F[i,j]$F[i,j] 表示前 $i$i 堆石子, $SG$SG 异或起来等于 $j$j 的方案数,

$F[i,j]=F[i-1,j⨁k]+sum\left[k\right]$F[i,j]=F[i−1,j⨁k]+sum[k]

发现可以使用 倍增 的方式优化,

$F[i,j]=F[i-1,j⨁k]\ast F[i-1,k]$F[i,j]=F[i−1,j⨁k]∗F[i−1,k]

时间复杂度 $O(logM\ast lo{g}^{2}N)$O(logM∗log2N),

得分 $50pts$50pts .

当 $N$N 和 $M$M 是大数时, 需要先使用 高精度 预处理出所有 $sum\left[\right]$sum[],
然后对于 $dp$dp 的转移, 发现是异或卷积的形式, 可以用 $FWT$FWT 优化, 没学过的可以看 这里 .

时间复杂度 $O\left(能过\right)$O(能过) .

得分 $100pts$100pts .

$实现部分$实现部分

有时间再补 .
咕咕咕 .