【51Nod 1149】Pi的递推式

2019-11-08 03:00:24

字体：大中小

来源：转载

供稿：网友

Description

F(x) = 1 (0 <= x < 4) F(n) = F(n - 1) + F(n - pi) (4 <= x) Pi = 3.1415926535….. 现在给出一个N，求F(n)。由于结果巨大，只输出Mod 10^9 + 7的结果即可。

Solution

之前在做斐波那契额数列的第n项的时候，可以考虑为从0开始，可以选择+1或+2，一直加到n的方案数。那么这道题也大同小异，从0开始可以+1或者+π $/pi$ ，直到第一次＞n-4的时候的方案数（为什么是第一次，因为从n选择-1或-pi，当小于4的时候就退出1了）那么在最后到达n-4的时候，可能是+1加进去的，也可能是+pi加进去的，所以要分类讨论一下。如果是+1加进去的，那么就要枚举+pi的次数，然后求出+1次数的上限，使得最后加到≤n-4，然后+1就可以突破。然后用组合数算一算就好了。如果是+pi加进去的，那么和上面类似，只不过是枚举+1的次数，然后求+pi的上限而已。

Code

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#include<math.h>#define fo(i,a,b) for(i=a;i<=b;i++)#define fod(i,a,b) for(i=a;i>=b;i--)typedef double db;typedef long long ll;using namespace std;const db pi=acos(-1);const int mo=1e9+7,maxn=1e6+7;int i,j,k,l,t,n,m;ll ans,fact[maxn],ni[maxn];db x,y;ll qsm(ll x,ll y){ ll z=1; for(;y;y/=2,x=x*x%mo)if(y&1)z=z*x%mo; return z;}ll c(ll x,ll y){ return fact[x]*ni[x-y]%mo*ni[y]%mo;}int main(){ fact[0]=ni[0]=1; fo(i,1,1000000)fact[i]=fact[i-1]*i%mo; ni[1000000]=qsm(fact[1000000],mo-2); fod(i,999999,1)ni[i]=ni[i+1]*(i+1)%mo; scanf("%d",&n); if(n<4){PRintf("1/n");return 0;} n-=4; fo(i,0,int(n*1.0/pi)){ t=(db)(n-i*pi); (ans+=c(t+i,i))%=mo; } fo(i,0,n){ t=(db)((n-i)/pi); (ans+=c(t+i,i))%=mo; } printf("%lld/n",ans);}

上一篇：LoadLibray失败，返回错误码193

下一篇：用c语言实现进度条

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注