ARC084D XorShift

题意 ：有 个数 写在黑板上（以二进制形式给出），现在有两种可以执行无限次的操作：

当 在黑板上时把 也写在黑板上。

当 和 都在黑板上时，把 写在黑板上。（选择的 可以相同）

求最终有多少个 的数能被写在黑板上。答案对 取模。

，，时限 。

---

将给出的数看做 下的多项式。

两个操作分别对应 “乘 ” 和 “两个多项式相加/减”。

利用这两个操作，可以构造出多项式 的 。

具体地，求 时，不妨设 ，记 。

则有 。

显然，这样的转化每次都会使得 的次数减少，故（当 其中一者为 时）能求得答案。

记 为 的 。不难发现，题目中的操作只能构造出所有 的倍数。

• 于是问题转化为：

  有多少个多项式 满足下列条件：

  • 是 的倍数。

  • 转化为二进制数后 。

根据数位 的套路，可以将第二个条件转化成若干如下不相交的约束 ：

• 钦定前面的若干高位，其余低位随意。

记 。若 则答案为 （仅有 符合条件）。

不难证明，若我们钦定了 的高位，只剩下 个低位没有钦定，那么有唯一一种方法填写低位使得其是 的倍数。

• 具体方法：记被钦定的部分为 ，在低位填上 。

于是，若询问中钦定了前 个高位，则 ：

• 若 ，方案数为 。

• 若 ，这些询问的前 位都是相同的（与 相同），只需处理一次。（补全后判定是否 ）

利用 std::bitset， 下的多项式 ，多项式取模的复杂度均可以做到 。

于是总复杂度为 。