题解 P2044 【[NOI2012]随机数生成器】

· · 题解

着重介绍一下求数列通项的不动点法。

形如x_{n+1}=ax_n+c的递推式是不动点法最简单且最经典的应用。

设不动点为k。

展开得$x_{n+1}=ax_n+k(a-1)$。 比较系数，得$c=k(a-1)

于是k=\frac{c}{a-1}

这样x_n+k就是一个等比数列，求通项得：

x_n+k=a^n(x_0+k) x_n=a^nx_0+(a^n-1)k x_n=a^nx_0+\frac{(a^n-1)c}{a-1}

接下来的问题是如何求\frac{(a^n-1)c}{a-1} \space \space mod \space \space m .

展开得\frac{(a^n-1)c}{a-1}=c*\sum_{i=0 \to {n-1}}a^i

只要求\sum_{i=0\to {n-1}}a^i即可。

\sum_{i=0 \to {n-1}}a^i =\sum_{i=0 \to {\frac{n-1}{2}}}a^i+\sum_{i={\frac{n-1}{2}+1} \to {n-1}}a^i =(1+a^{\frac{n+1}{2}})\sum_{i=0 \to {\frac{n-1}{2}}}a^i

递归求解即可。其中乘法部分要用龟速乘。

代码：


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

long long mod,n,a,c,x,g;

long long mul(long long x,long long y)
{
    long long ret=0,bas=x;
    while(y)
    {
        if(y&1)
        {
            ret+=bas;
            if(ret>=mod) ret-=mod;
        }
        bas+=bas;if(bas>=mod) bas-=mod;
        y>>=1;
    }
    return ret;
}

long long F_p(long long x,long long y)
{
    long long ret=1,bas=x;
    while(y)
    {
        if(y&1) ret=mul(ret,bas);
        bas=mul(bas,bas);
        y>>=1;
    }
    return ret;
}

long long solve(long long mx)
{
    if(!mx) return 1;
    long long tt=solve(mx>>1);
    long long pp=mul(tt,F_p(a,(mx>>1)+1));
    tt+=pp;if(tt>=mod) tt-=mod;

    if(!(mx&1))
    {
        tt-=F_p(a,mx+1);
        if(tt<0) tt+=mod;
    }
    return tt;
}

int main()
{
    scanf("%lld%lld%lld%lld%lld%lld",&mod,&a,&c,&x,&n,&g);

    a%=mod,c%=mod,x%=mod;

    long long fz=solve(n-1);
    fz=mul(fz,c);

    x=mul(x,F_p(a,n));

    x+=fz;if(x>=mod) x-=mod;

    printf("%lld\n",x%g);
    return 0;
}