传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3992 思路：M是一个质数，问题又是求乘积，于是我们就可以想到利用M的原根g把问题变成求和（我怎么想不到啊。。。） 根据原根的性质，我们可以把1到M-1中的数i表示为(g^b[i])%M，且指数互不相同 那么X就可以表示成(g^b[x])%M 问题就转化为：然后问题转化成了在序

传送门 这个题大概裸dp这样：dp(i,j)代表已经填了前i个位置，当前乘积为j的方案数C(k)代表集合S中是否存在kdp(i+1,j∗k%m)=∑kdp(i,j)∗C(k)然后这个dp是O(m2n)的，也没啥优化的办法我们尝试将∗转化成+原根是个不错的选择原根可以将m−1个不同的数字(这个题目里0可以不计)对应到m−1个不同的幂上所以我们对应了之后，dp方程就改变了：dp(i+1,(j