F(x) = 1 (0 <= x < 4)
F(x) = F(x - 1) + F(x - pi) (4 <= x)
Pi = 3.1415926535.....
现在给出一个N，求F(N)。由于结果巨大，只输出Mod 10^9 + 7的结果即可。
Input
输入一个整数N(1 <= N <= 10^6)
Output
输出F(N) Mod 10^9 + 7
Input示例
5
Output示例
3
组合数+思路~
神奇的问题。
我们发现答案相当于是所有从[0,4)走到n的方案数，所以我们枚举走pi的步数判断是否可行，再用组合数求出答案。
但是边界想起来好麻烦QAQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long longconst int mod=1e9+7;
const double pi=acos(-1);int n,sheng[1000001],jiang[1000001],ans;int mi(int u,int v)
{int now=1;for(;v;v>>=1,u=(ll)u*u%mod) if(v&1) now=(ll)now*u%mod;return now;
}int c(int n,int m)
{return n<m ? 0:(ll)sheng[n]*jiang[m]%mod*jiang[n-m]%mod;
}int main()
{scanf("%d",&n);if(n<4){puts("1");return 0;}sheng[0]=jiang[0]=1;for(int i=1;i<=n;i++) sheng[i]=(ll)sheng[i-1]*i%mod;jiang[n]=mi(sheng[n],mod-2);for(int i=n-1;i;i--) jiang[i]=(ll)jiang[i+1]*(i+1)%mod;for(int i=0,j;i<=(n-4)/pi;i++){j=(int)n-4-pi*i;do{if(j+i*pi>n-4-1) ans=(ans+c(i+j,j))%mod;if(j+i*pi>n-4-pi) ans=(ans+c(i+j,j))%mod;j--;}while(j+i*pi>n-4-pi);}printf("%d\n",ans);return 0;
}