P9816 少项式复合幂 题解

简要题意

称一个项数小于等于 \(20\) 的多项式为一个少项式。

求一个少项式的 \(y\) 次复合函数在 \(x\) 点上 \(f_{y}(x)\bmod p\) 的值。

解题思路

题目强调注意 \(m,p\) 的范围，观察发现 \(p\) 的范围在 \(10^5\) 之内。

关于模运算，它拥有以下显然的性质：

$$ (x + y)\bmod p = (x\bmod p + y\bmod p) $$

$$ (x \times y)\bmod p = ((x\bmod p)\times (y\bmod p))\bmod p $$

所以对于一个多项式函数有等式 \(f(x) \bmod p = f(x\bmod p)\bmod p\) 存在。不明白的想想你的快速幂为什么对。

$$ f(x)\bmod p = \sum_{i = 1}^{m} a_i x^{b_i} \bmod p = \sum_{i = 1}^{m} (a_i (x\bmod p)^{b_i} \bmod p) \bmod p $$

如上柿我们可以用 \(O(m\log\max{b})\) 的时间预处理出所有 \(0\le x < p\) 的 \(f(x)\bmod p\) \(O(1)\) 地快速进行回答。

然后应该初学者都能想到通过 \(y\) 次迭代求得 \(f_y(x)\bmod p\) 关键在于将迭代的复杂度降低。

考虑进行倍增，因为有 \(f_{2^k}(x) = f_{2^{k - 1}}(f_{2^{k - 1}}(x))\)

令 \(st_{x,k} = f_{2^k}(x)\) 则我们可以通过 \(O(\log y)\) 的迭代求得答案。

$$ st_{x,k} = \begin{cases} f(x)\bmod p & k = 0 \\ st_{st_{x,k - 1},k - 1} & \mathrm{Otherwise.} \\ \end{cases} $$

需要注意的是，因为 \(y\le 10^7\) 因此枚举 \(k\) 直到 \(2^k > 10^7\)。

贴个代码

这里令 \(f_{x,k} = st_{x,k}\)。

#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
constexpr int Y = 1e7 + 10;

rep (i, 0, p - 1)
    rep (j, 1, m)
        f[i][0] = (f[i][0] + 1ll * a[j] * fpow(i, b[j]) % p) % p;

for (int j = 1; (1 << j) <= Y; ++j)
    rep (i, 0, p - 1)
        f[i][j] = f[f[i][j - 1]][j - 1];

rep (i, 1, q)
{
    cin >> x >> y; x %= p;
    for (int k = 30; ~k; --k)
        if ((1 << k) & y) x = f[x][k];
    cout << x << endl;
}