#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ui unsigned int
using namespace std;
const int K=5e4+10,M=210,N=1e4+10;
const int p=998244353;
int n;
ull dp[N][10];
int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-48;s=getchar();}
return x*f;
}
int main()
{
n=read();
dp[0][1]=1,dp[1][2]=1,dp[1][1]=1;
for(int i=2;i<=n;i++)
{
if(i>=2)
dp[i][3]=dp[i-2][1];
if(i>=2)
dp[i][4]=dp[i-2][4]+dp[i-2][3];
if(i>=4)
dp[i][4]+=dp[i-4][3];
dp[i][2]=dp[i][3]+dp[i-1][5];
if(i>=2)
dp[i][5]=dp[i-2][5]+dp[i-2][4];
dp[i][5]+=dp[i][4];
for(int j=0;j<i;j++)
dp[i][1]+=dp[j][1]*dp[i-j][2];
}
printf("%llu",dp[n][1]);
return 0;
}
原文链接: https://www.cnblogs.com/dingxingdi/p/15507197.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/214682
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!