两行代码就解决（bushi

非打表
40ms 1.44MB

#include <bits/stdc++.h>
using namespace std;const int MOD=1e9+7;long long p1=1,p2=2,p3=4,n,k;inline int read(){int s=0;char ch=getchar();while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s;}inline void write(int x){if(x>9) write(x/10);putchar(x%10+'0');}int main(){n = read();for (int i=4;i<=n;i++){k=p1+p2+p3;p1=p2;p2=p3;p3=k%MOD;}write(p3);return 0;}