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
",ret);
    return 0;
}

NOI 2012 随机数生成器

相关推荐