听说有个人差，但我觉得是倍增典题。

题目链接

给定多项式 ，记 ，。

次询问，每次询问给出 ，求 的值。

• ；
• ；
• ，保证 为质数；
• ；
• 。

---

注意到 均较小，考虑将函数的映射表打出来。

使用一个倍增将 的映射表也打出来。

显然有 ，因此单次查询时可以 次把所求函数拼出来。

可以结合图上一些倍增手法或快速幂的倍增理解。