NOI 2012 随机数生成器

看到全是矩阵的题解，我来一发递推+分治

其实这题一半和poj1845很像（或是1875？一个叫Sumdiv的题）

言归正传，我们看看怎么由f(0)推出f(n)

我们发现，题目中给出了f(n)=af(n-1)+c（取模略过）

那么顺着递推，可得：f(n-1)=af(n-2)+c

代入，得：

f(n)=a^2 f(n-2)+(a+1)c

继续递推，得：

f(n)=a^n f( 0 )+(a^ (n-1)+a^ (n-2)+...+1) c

左半部分，我们可以直接快速幂求a^n，再乘f(0)即可

右半部分，我们可以分治求出系数和。

怎么求？

我们发现，a^3+a^2+a+1=(a^2+1)(a+1)

那么对于任意奇次的推广，我们都可以如此因式分解，同时左半侧快速幂，右半侧递归求解即可。

而对于偶次，仅需将最高次项单独计算，剩下项继续递归即可

但要注意本题模数太大，乘法会直接爆long long，所以需要用到快速加（将乘法转化成加法快速幂的思想）

（PS：其实右半部分的分治可以用等比数列求和公式解决，但好像需要求逆元，会增大算法难度，所以直接分治解决就好）

贴代码

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <queue>

#include <stack>

#define ll long long

using namespace std;

ll m,a,c,x0,n,g;

ll pow_add(ll x,ll y)

{

    ll ans=0;

    while(y)

    {

        if(y%2)

        {

            ans=(ans+x)%m;

        }

        x=(x+x)%m;

        y/=2;

    }

    return ans%m;

}

ll pow(ll x,ll y)

{

    ll ans=1;

    while(y)

    {

        if(y%2==1)

        {

            ans=pow_add(ans,x);

        }

        x=(ll)pow_add(x,x)%m;

        y/=2;

    }

    return ans%m;

}

ll quick_sum(ll x,ll y)

{

    if(y==1)

    {

        return (x+1)%m;

    }

    if(y==0)

    {

        return 1;

    }

    if(y%2)

    {

        return pow_add((pow(x,y/2+1)%m+1)%m,quick_sum(x,y/2)%m)%m;

    }

    return pow(x,y)%m+pow_add((pow(x,y/2)+1)%m,quick_sum(x,y/2-1)%m)%m;

}

int main()

{

    scanf("%lld%lld%lld%lld%lld%lld",&m,&a,&c,&x0,&n,&g);

    x0%=m;

    ll a0=pow(a,n)%m;

    ll temp1=pow_add(a0,x0)%m;

    ll temp2=pow_add(quick_sum(a,n-1)%m,c%m)%m;

    ll ret=(temp1+temp2)%m%g;

    printf("%lld\n",ret);

    return 0;

}

巴特西

NOI 2012 随机数生成器

最新文章

热门文章