P9816 少项式复合幂题解

· · 题解

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;
}