【SDOI2015】序列统计


题意

从集合 \(S\) 中可重的选择 \(n\) 个数组成数列,求数列的乘积模 \(m\) 为 \(x\) 的数量。

分析

不考虑数的大小的话,很容易想到一个 dp 。

\(f[i][j]\) 表示处理了前 \(i\) 个数,乘积为 \(j\) 的方案数。显然这样的第二维太大了,于是考虑化乘积为和。

乘积为和的方法显然就是求对数了,但直接求对数涉及到浮点数问题,又发现 \(M\) 是质数,于是考虑用离散对数来做。

我们令 \(g\) 为 \(M\) 的原根,显然对于每一个 \(a_i\) 可以转化成 \(g^{b_i}\) 。

于是现在就变成了求 \(\sum _{i=1}^{|S|}b_i\equiv x\equiv (mod \; M-1)\) 的方案数。

考虑用 NTT 来优化转移即可。

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 61,990

Categories

Archive

Comments