bzoj3992

转移自老blog

bzoj3992

链接

题意

        小C有一个集合S,里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为N的数列,数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数x,求所有可以生成出的,且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为,两个数列{Ai}和{Bi}不同,当且仅当至少存在一个整数i,满足Ai≠Bi。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

题解

        dp[i][j]前i个数积为j的方案数,答案在dp[N][X]
        dp[i][j]=dp[i-1][j/S[1]]+dp[i-1][j/S[2]]...
        换成原根就成了减法,然后构造一个多项式,发现dp[i]=dp[i-1]*u
        最后dp[i]=dp[1]*u^(n-1)
        用快速幂加速NTT