#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <math.h>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 1e5+10
using namespace std;
int dp[1010][3];
int main()
{
    int n;
    scanf("%d",&n);
    dp[1][0]=1;
    dp[1][1]=1;
    dp[2][0]=2;
    dp[2][1]=1;
    dp[2][2]=1;
    for(int i=3;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2];
        dp[i][0]%=55555;
        dp[i][1]=dp[i-1][0];
        dp[i][2]=dp[i-1][1];
    }
    printf("%d",(dp[n][0]+dp[n][1]+dp[n][2])%55555);
    return 0;
}

点个赞呗！！！

天啊，我写了个递归居然过了，必须吐槽数据好吧

赶紧加强啊

该题比较难，但通过找规律可以发现，从第四个数开始，该数的值为前三个数之和。n=1时，方案数为2；n为2时，方案数为4；n=3时，方案数为7;再根据规律递归依次求出n即可。（本蒟蒻第一次写题解）