原根 + 背包 + bitset优化 + 二进制分组：0115B

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135609260

http://47.92.197.167:5283/contest/451/problem/2

原根： $g^1,\dots,g^{p-1}$ 在 $\bmod p$ 意义下取遍 $1\sim p-1$ 。在 $p$ 为质数时， $g$ 不超过 $p^{\frac 1 4}$

因此此题我们可以暴力求原根

然后对于每个数就变成了加法问题。现在是 $n$ 个物品，空间为 $p$ 的01背包问题，可以采用bitset优化。

物品种类不超过 $p$ 种，可以变成多重背包然后二进制分组优化。

复杂度是 $O(\frac{p^2\log n\log p}\omega)$ 的。

题解有神秘做法，长大回来学：