首页 > 代码库 > 【2017 4 24 - B】 组合数
【2017 4 24 - B】 组合数
【题目描述】
输入格式：
一行一个正整数n
输出格式：
一行一个数f(n)对1000000007取余的值
【分析】
就是乱搞？？
就是问根到叶子有多少条路径嘛。
然后路径可以π、1、1、π...这样表示
枚举有多少个$π$，算出最后一个π前面最多多少个1【这样比较不容易算重复什么的】，然后用组合数算一算。
有一个比较坑的地方就是比如3.2是-π是大于0但是是不能减的因为3.2已经小于4了。
然后就是假设枚举了i个π，最后一个π前面最多y个1.
就是
$\sum_{j=0}^{y} C_{i+j-1}^{i-1}$
这是个很经典的数学题？
就是在前面加一个$C_{i+j}^{i}$,然后两项并一起得出来就是$C_{i+y}^{i}$
求和即可。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #include<cmath> 7 using namespace std; 8 #define Mod 1000000007 9 #define LL long long 10 const double pi=acos(-1); 11 #define Maxn 1000010 12 13 int fac[2*Maxn],inv[2*Maxn]; 14 15 void init(int n) 16 { 17 fac[0]=1;for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%Mod; 18 inv[1]=1;for(int i=2;i<=n;i++) inv[i]=1LL*(Mod-Mod/i)*inv[Mod%i]%Mod; 19 inv[0]=1;for(int i=1;i<=n;i++) inv[i]=1LL*inv[i]*inv[i-1]%Mod; 20 } 21 22 int get_c(int n,int m) 23 { 24 if(n<m) return 0; 25 int ans=1LL*fac[n]*inv[m]%Mod; 26 ans=1LL*ans*inv[n-m]%Mod; 27 return ans; 28 } 29 30 31 int main() 32 { 33 int n,ans=0; 34 scanf("%d",&n); 35 init(2*n); 36 for(int i=1;i<=n;i++) 37 { 38 int y=(int)floor(n-i*pi); 39 if(n-i*pi-y<4-pi) y--; 40 ans=(ans+get_c(i+y,i))%Mod; 41 }ans=(ans+1)%Mod; 42 printf("%d\n",ans); 43 return 0; 44 }
【这题有毒，有时错有时对？？
2017-04-24 20:30:36
【2017 4 24 - B】 组合数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。