题意

给定 $n,p$ 和长度为 $n$ 的整数序列 $a$ ，你需要输出整数序列 $b$ 满足：

1. $b_i\in \{-1,0,1\}$ 且不全为 $0$ 。
2. $\sum a_ib_i\equiv 0\pmod p$

保证 $2^n\gt p$ 。

$1\leq p\lt 2^n, 1\leq n\leq 40,0\leq a_i\lt p$ 。

口胡

考虑转化一下问题：相当于要搜出两个只含 0,1 的序列，然后使得它们相减的差模 $p$ 为 0，也就是让它们的和相同（模 $p$ 意义下）。如此会有 $2^n$ 种方法，而只要求 $p$ 种和，根据鸽笼一定有解。

假设有 $p$ 个桶共有 $2^n$ 个子集和，则桶装了超过 1 个的就是符合要求的。则令 $s_{l,r}$ 表示区间 $[l,r]$ 内的桶装了的子集数。若 $s_{l,r}>r-l+1$ ，那么左半边或右半边一定也可以满足，即可二分得到答案。

对于 $s_{l,r}$ 的求解可以折半搜索把两边的情况搜出来，然后双指针找到结果。

$\mathcal{O}(n^{\frac{n}{2}}\log p)$ 。