【星河(star)】题解([star] solution)

题目:

一个函数 \(f(x)\) 的定义为:

特别地,\(f(0)=f(1)=1\)。小 A 给出一个非负整数 \(n\),请你帮他求出 \(f(n)\) 对 \(998244353\) 取模的结果。

解法:

可以发现,除了 \(1,2,3\),对于 \(x\) 为偶数,\(f(x)=f(x+1)\)。那么 \(f(x+2)\) 就是 \((f(1)+…+f(x-2))+f(x)=2f(x)\),即 \(f(x)=2^{\frac{x}{2}-1}\)。运用快速幂求解即可。证明可以看作数学归纳法。

————————

Title:

A function \ (f (x) \) is defined as:

In particular, \ (f (0) = f (1) = 1 \). Small a gives a nonnegative integer \ (n \), please help him find the result of \ (f (n) \) modulo \ (998244353 \).

Solution:

It can be found that except for \ (1,2,3 \), for \ (x \) is even, \ (f (x) = f (x + 1) \). Then \ (f (x + 2) \) is \ ((f (1) ++ F (X-2)) + F (x) = 2F (x) \), i.e. \ (f (x) = 2 ^ {\ frac {x} {2}-1} \). It can be solved by fast power. Proof can be regarded as mathematical induction.