首页 > 代码库 > 【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 }
View Code

 

【这题有毒,有时错有时对??

 

2017-04-24 20:30:36

【2017 4 24 - B】 组合数