https://www.luogu.org/problem/show?pid=U3357
題目背景
在你成功地解決了上一個問題之后，方方方不禁有些氣惱，于是他在樓梯上跳來跳去，想要你求出他跳的方案數。..
題目描述
方方方站在一個n階樓梯下面，他每次可以往上跳一步或兩步，往下跳一步到四步（由于地心引力跳得比較遠），而且在往下跳的時候你只能踩在你往上跳時踩過的格子。
現在方方方在樓梯上亂跳，想問他跳到樓梯頂上最后又跳回樓梯下面的方案數mod 2333333。
請注意：針對題目有歧義的情況，這里再說明一下。方方方只能一直向上跳，跳到樓梯最上面，然后再往下跳，跳回樓梯最底下。
輸入輸出格式
輸入格式：
?
輸入一行一個數n。
?
輸出格式：
?
輸出方方方跳回樓梯下面的方案數mod 2333333。
?
輸入輸出樣例
輸入樣例#1：
5
輸出樣例#1：
52
輸入樣例#2：
7654321
輸出樣例#2：
451197
輸入樣例#3：
3
輸出樣例#3：
8
說明
對于30%的數據，n<=10。
對于100%的數據，1<=n<=10^7。
?
向下走可以看成向上走
f[i]表示第一次向上走到i，第二次向上也走到i的方案數
如果第二次向上走1步到i，這1步第一次有1種走法
如果第二次向上走2步到i，這2步第一次有2種走法
如果第二次向上走3步到i，這3步第一次有3種走法
如果第二次向上走4步到i，這4步第一次有5種走法
所以狀態轉移方程：f[i]=f[i-1]+f[i-2]*2+f[i-3]*3+f[i-4]*5
?
#include<cstdio> #define N 10000001 #define mod 2333333 using namespace std; int f[N]; int main() {int n;scanf("%d",&n);f[0]=1; f[1]=1; f[2]=3; f[3]=8;for(int i=4;i<=n;i++) f[i]=(f[i-1]+f[i-2]*2+f[i-3]*3+f[i-4]*5)%mod;printf("%d",f[n]); }
?
