妙?
H
题意:
给定长为$n$的格雷码$G^{(n)}[i]$的定义,给定一个二进制数$x$,定义$S(x)=G^{(n)}[x]$,求$S_{k}(x)$。
题解:
我们首先要找到格雷码的规律,不管他的长度是多少,都有$G[x]=x\oplus (x>>1)$。
有这个性质的话,我们可以发现我们要求的就是对于最初的$x_i$,其$i,i+1,\dots,i+k$位对其的贡献是多少,通过打表观察发现满足组合数,$\binom{k}{0},\binom{k}{1},\dots,\binom{k}{k}$。
而在异或当中我们只需要看其$\mod 2$的值即可,而由卢卡斯定理我们可以知道,当且仅当$k\&j==j$时即$j$是$k$的子集的时候,$j$对$i$才有贡献。
那么我们就可以直接将子集拆成对$k$每一位二进制的$dp$,则有。
($j$表示是$k$当前的低$j$位。)
复杂度为$O(nlogk)$,用$bitset$则为$O(\frac{nlogk}{w})$。
- 本文作者: baddog
- 本文链接: https://katoli.github.io/2022/07/05/2022JSCPC/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!