nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
转移自老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