RainAir
My OI Blog
RainAir
「CF1106F」Lunar New Year and a Recursive Sequence

题目链接
首先 $f_{[1\cdots k-1]} = 1$,所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。
我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解,然后就是解方程 $$f_k^e \equiv m (\mod 998244353)$$ 了。
这是一个简单的离散对数入门题,我们就两边取个 $log_g$
$$(log_g f_k)e \equiv log_g m(\mod \varphi(998244353))$$
然后因为 $g = 3$,用 BSGS 算出两项,最后用 exgcd 解出 $e$ 直接代入即可。
代码:

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/743
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
首页      题解      「CF1106F」Lunar New Year and a Recursive Sequence
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF1106F」Lunar New Year and a Recursive Sequence
题目链接 首先 $f_{[1\cdots k-1]} = 1$,所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解,然后就是解方程 $$f_k^e \equiv m (\mod 9…
扫描二维码继续阅读
2019-08-01
标签
近期评论