比赛链接

EOJ Monthly 2021.9 Sponsored by TuSimple

A. Amazing Discovery

单点时限: 1.0 sec

内存限制: 1024 MB

题目描述

Siyu recently made an amazing discovery. If \(a,b,n\) are all positive integers, then

is also a positive integer.

To verify his discovery, please print \(S\) modulo 998244353.

输入格式

The only line contains three integers \(a,b\) and \(n (1 \leq a,b,n \leq 10^9)\).

输出格式

Print on a line \(S\) modulo 998244353.

样例

input

1 2 3

output

14

解题思路

分治，记忆化

我们可以推导出这样的式子：

为防止不必要的重复计算，我们可以记忆化
这里需要额外注意的一点是，快速幂的底数可能为负数，需要转换一下~

• 时间复杂度:\(O(logn)\)

代码

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL mod=998244353;
unordered_map<int,LL>mp;
LL ksm(LL a,int b)
{
    a=(a%mod+mod)%mod;
    LL res=1%mod;
    for(;b;b>>=1)
    {
        if(b&1)res=res*a%mod;
        a=a*a%mod;
    }
    return res;
}
LL a;
int b,n;
LL cal(int n)
{
    if(mp.find(n)!=mp.end())return mp[n];
    if(n==0)return 2;
    if(n==1)return 2*a;
    if(n&1)
    {
        int x=n/2,y=n-x;
        return mp[n]=(cal(x)*cal(y)%mod-2*a%mod*ksm(a*a-b,x)%mod+mod)%mod;
    }
    LL tmp=cal(n/2);
    return mp[n]=(tmp*tmp%mod-2*ksm(a*a-b,n/2)%mod+mod)%mod;
}
int main()
{
    scanf("%d%d%d",&a,&b,&n);
    printf("%lld",cal(n));
    return 0;
}

EOJ Monthly 2021.9