51nod1149 Pi的递推式

基准时间限制：1 秒空间限制：131072 KB 分值: 640

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示例

Output示例

数学问题递推组合数

实数下标的递推，甚至不能记忆化（吧？），递归显然不可取。

可以先考虑一般的情况。

比如Fibonacci数列的递推式是 $ F[n]=F[n-1]+F[n-2] $

众所周知，它的组合数意义可以解释为任选走一级或走两级，从0级上到n级台阶的方案数。（然而蒟蒻博主就不知道）

由此得出F[n]的另一个计算方式是枚举走两级走了i次，然后 $F[n]=\sum_{i=0}^{n/2} C(n-2i+i,i) $

这个算法可以推广到一般的递推式。

那么在本题中，可以类似地枚举走1和走pi的次数，累计从0走到大于n-4的位置的方案数。

由于枚举走1或枚举走pi时，另一个走法的次数上限不同（第一次到达>n-4的位置时，到达的具体位置不同），所以要分类讨论。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define LL long long

 using namespace std;

 const double pi=acos(-1.0);

 const int mxn=;

 const int mod=1e9+;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int ksm(int a,int k){

     int res=;

     while(k){

         if(k&)res=(LL)res*a%mod;

         a=(LL)a*a%mod;

         k>>=;

     }

     return res;

 }

 int fac[mxn],inv[mxn];

 void init(int ed){

     fac[]=fac[]=;inv[]=inv[]=;

     for(int i=;i<=ed;i++)

         fac[i]=(LL)fac[i-]*i%mod;

     inv[ed]=ksm(fac[ed],mod-);

     for(int i=ed-;i;i--)

         inv[i]=(LL)inv[i+]*(i+)%mod;

     return;

 }

 inline int C(int n,int m){

     if(n<m)return ;

     return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod;

 }

 int n;

 int ans=;

 int main(){

     int i,j;

     n=read();

     if(n<){

         printf("1\n");return ;

     }

     init(n);

     for(i=;i<=n-;i++){//

         int tmp=(int)(((double)n--i)/pi);

 //        printf("i:%d tmp:%d %d\n",i,tmp,C(tmp+i,i));

         (ans+=C(tmp+i,i))%=mod;

     }

     for(i=;i*pi<=n-;i++){//pi

         int tmp=(int)(n--i*pi);

 //        printf("i:%d tmp:%d %d\n",i,tmp,C(tmp+i,i));

         (ans+=C(tmp+i,i))%=mod;

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

51nod1149 Pi的递推式

最新文章

热门文章