P2044 [NOI2012]随机数生成器

题意：生成一个数列并求序列第$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; } ```