FZU 2015 Vote

Problem Description

Here are n Candidates in one election. Every Candidate could vote any one (of course himself/herself). In this election, the one who gets more than half of n become the winner! However, sometimes no winner could be determined (No one gets more than half of n votes)!

Now you are given the number of Candidates and the final winner m, here if m is equal to -1, then it means that no one wins, otherwise m is the index of the Candidate. (The index of Candidates is 0, 1, 2, … n – 1 respectively) Abcdxyzk wants to know the number of possible ways of the final result if the winner if m. (m = -1 for no winner of course) However, the answer maybe large, so abcdxyzk just want the remainder of the answer after divided by 1000000007.

Input

There are several test cases.

For each case, only two integers n and m in a single line indicates n Candidates and the final winner m. (1 <= n <= 100, -1 <= m < n)

Output

For each test case, output the number of possible ways of the final election!

Sample Input

2 1 3 -1 4 1

Sample Output

1 1 4

Hint

In case 1, only one possible ways of the final result because both 0 and 1 vote to 1.

In case 2, only one possible ways of the final result because all of 0, 1, and 2 get one vote.

In case 3, there are 4 possible ways of final result:

(1) 0: 1 (vote(s)) 1: 3 (vote(s)) 2: 0 (vote(s)) 3: 0 (vote(s))

(2) 0: 0 (vote(s)) 1: 3 (vote(s)) 2: 1 (vote(s)) 3: 0 (vote(s))

(3) 0: 0 (vote(s)) 1: 3 (vote(s)) 2: 0 (vote(s)) 3: 1 (vote(s))

(4) 0: 0 (vote(s)) 1: 4 (vote(s)) 2: 0 (vote(s)) 3: 0 (vote(s))

-----------------------------------------------------------分-割-线--------------------------------------------------------------

一道组合数的问题，如果有人赢，则他至少有 n / 2 + 1 张选票，剩下的nn张选票可以分给一个人，两个人，，，对多nn个人，用组合数选出人，乘上隔板法的分割情况数，最后求和。如果没有人赢，则用上述方法求出有人赢得所有情况，在用所有投票情况减去有人赢的情况就是答案。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 const long long int mod = 1000000007;
 7 const int maxn = 110;
 8 long long combin[maxn][maxn];
 9 void init() { ///初始化打出组合数表
10     for(int i = 0 ; i < maxn ; i++) combin[i][0] = 1;
11     combin[1][1] = 1;
12     for(int i = 2 ; i <= 100 ; i++)
13         for(int j = 1 ; j <= i ; j++)
14             combin[i][j] = (combin[i - 1][j - 1] + combin[i - 1][j]) % mod;
15 }
16 long long slove(int n) { ///返回n个人中有一个人赢得情况数对mod的模
17     long long int ans = 0;
18     long long int nn = n - (n / 2 + 1);
19     if(n == 2 || n == 1) ans = 1;
20     for(int i = 1 ; i <= nn ; i++)
21         ans += combin[n][i] * combin[nn - 1][i - 1] % mod, ans %= mod;
22     return ans;
23 }
24 int main()
25 {
26     int n, m;
27     init();
28     while(scanf("%d%d", &n, &m) == 2) {
29         if(m < 0) {
30             long long int ans1 = 0;
31             for(int i = 1 ; i <= n ; i++) ans1 += combin[n][i] * combin[n - 1][i - 1] % mod, ans1 %= mod;
32             long long int ans = slove(n);
33             printf("%I64d\n",(ans1 - (ans * n % mod) + mod) % mod);
34         }
35         else {
36             printf("%I64d\n", slove(n));
37         }
38     }
39     return 0;
40 }