P2044 [NOI2012]随机数生成器

2018-09-28 16:35:12


题意:生成一个数列并求序列第 $n$ 项对 $p$ 取模的值

   序列生成方式: $A_{i}=(a*A_{i-1}+c)\%m$


经过一番推算,可以得到:

$A_n=a^n*A_0+c+ac+a^2c+...+a^{n-1}c$

第一项可以用快速幂得到

后面是一个等比数列

求和公式有除法运算,无法直接取模

正确的姿势如下

求公比为 $k$ 的等比数列前 $n$ 项和:

$n$ 为偶数: $Sum(n)=Sum(n/2)+Sum(n/2)*Pow(k,n/2)$

$n$ 为奇数: $Sum(n)=Sum(n/2)+Sum(n/2)*Pow(k,n/2)+$ 数列第 $n$ 项的值

用递归求解

注意中间过程可能爆 $ll$ ,用龟速乘就可以了

#include<cstdio>
typedef unsigned long long ll;
ll n,mod,a,c,x,p;
ll multi(ll n,ll k)
{
    ll s=0;
    while (k)
    {
        if (k&1) s=(s+n)%mod;
        n=(n+n)%mod; k>>=1;
    }
    return s;
}
ll quickpow(ll n,ll k)
{
    ll s=1;
    while (k)
    {
        if (k&1) s=multi(s,n);
        n=multi(n,n); k>>=1;
    }
    return s;
}
ll Sum(ll n,ll t)
{
    if (n==1) return t;
    ll res=Sum(n/2,t);
    res=(res+multi(res,quickpow(a,n/2)))%mod;
    if (n&1) res=(res+multi(quickpow(a,n-1),t))%mod;
    return res;
}
int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&mod,&a,&c,&x,&n,&p);
    ll ans=quickpow(a,n); ans=multi(ans,x);
    printf("%lld\n",(ans+Sum(n,c))%mod%p);
    return 0;
}