自动搬运

查看原文

来自洛谷，原作者为

	znszns **

搬运于2025-08-24 22:52:05，当前版本为作者最后更新于2023-10-30 14:57:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9816 少项式复合幂题解

题目传送门

$35$ 分做法

先注意题目加粗的字，提示我们应该考虑 $p$ 的范围。

预处理

显然 $f(x)\equiv f(x\bmod\ p)(\bmod\ p)$，所以考虑预处理 $f(x)\bmod p$，$f(x)=\sum_{i=1}^ma_ix^{b_i}$，$x$ 范围为 $0$ 到 $p-1$，时间复杂度为 $\Theta(mp\log{bi})$。

查询操作

直接一次一次跳，暴力跳 $y$ 次找到 $f_y(x)\bmod p$，时间复杂度为 $\Theta(qy)$。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int m,q;
ll mod,f[N],a[N],b[N];
ll qpow(ll x,ll y)
{
	ll res=1;
	for(;y;y>>=1,x=x*x%mod)
	{
		if(y&1) res=res*x%mod;
	}
	return res;
}
int main()
{
	scanf("%d%d%lld",&m,&q,&mod);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&a[i],&b[i]);
	for(int i=0;i<mod;i++)
	{
		for(int j=1;j<=m;j++)
		{
			f[i]=(f[i]+a[j]*qpow(i,b[j])%mod)%mod;
		}
	}
	ll x,y,ans;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		ans=f[x%mod];
		for(int j=2;j<=y;j++)
		{
			ans=f[ans];
		}
		cout<<ans<<endl;
	}
	return 0;
}

$100$ 分做法

可以发现查询操作若为 $\Theta(q\log{y})$ 是可以过的，于是先求出 $y$ 的二进制表示，比如说要跳 $10$ 次，相当于先跳 $2^1$ 次，再跳 $2^3$ 次。

预处理

用 $dp(i,j)$ 表示 $f(x)$ 跳 $2^j$ 次的结果，转移为 $dp(i,j)=dp(dp(i,j-1),j-1)$。

查询操作

把 $y$ 用二进制表示，最低位是第 $0$ 位，若第 $i$ 位为 $1$，设当前答案为 $ans$，$ans$ 则跳到 $dp(ans,i)$，表示跳了 $2^i$ 次，最后输出 $ans$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,M=25;
int m,q;
ll mod,f[N][M],a[N],b[N];
ll qpow(ll x,ll y)
{
	ll res=1;
	for(;y;y>>=1,x=x*x%mod)
	{
		if(y&1) res=res*x%mod;
	}
	return res;
}
int main()
{
	scanf("%d%d%lld",&m,&q,&mod);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&a[i],&b[i]);
	for(int i=0;i<mod;i++)
	{
		for(int j=1;j<=m;j++)
		{
			f[i][0]=(f[i][0]+a[j]*qpow(i,b[j])%mod)%mod;
		}
	}
	for(int j=1;j<M;j++)
	{
		for(int i=0;i<mod;i++)
		{
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	ll x,y,ans,cnt;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld%lld",&x,&y);
		cnt=0;
		ans=x%mod;
		while(y)
		{
			if(y&1) ans=f[ans][cnt];
			cnt++;
			y>>=1;
		}
		cout<<ans<<endl;
	}
	return 0;
}