9243的蒟蒻解法

常规
1

爬楼梯

Problem ID: 9243

Contest ID: 6189

Time Limit:

2000ms

Memory Limit:

256000kb

题目描述

一段楼梯有n级台阶。你每次可以爬一格、走两格或者跨三格。问你最终有几种方案？答案对998244353取模。

输入格式

一行一个数n。

输出格式

一行一个数，表示方案数。

样例

Input 1

3

Output 1

4

数据范围

n≤1000

为解决这个问题，我们可以使用动态规划来计算爬楼梯的方案数。设dp[i]表示到达第i级台阶的方案数。

对于第i级台阶，我们可以从第i-1级、第i-2级或第i-3级跳到第i级台阶，因此方案数为dp[i] = dp[i-1] + dp[i-2] + dp[i-3]。

由于要对答案取模，我们需要在计算过程中保持取模操作，避免整数溢出。

2 个赞
2

考虑一下 n\le10^{18} 怎么做

2 个赞
3

滚数组

2 个赞
4

不是这样的，你应该矩阵快速幂

\left(\begin{matrix}f_i\space f_{i+1}\space f_{i+2}\end{matrix}\right)\times \left(\begin{matrix}0\space0\space1\\ 1\space 0\space 1\\ 0\space 1\space 1\end{matrix}\right)=\left(\begin{matrix}f_{i+1}\space f_{i+2}\space f_{i+3}\end{matrix}\right)

大抵是 \mathcal{O}(\log n) 的

3 个赞
5

谢谢，我会学习的

1 个赞
6

加油

2 个赞
7

可以来这里学习

2 个赞