coreBugZJ

此 blog 已弃。

Vote， FZU 2011年3月月赛之 F， FZU 2015

Problem 2015 Vote

Time Limit: 1000 mSec    Memory Limit : 32768 KB

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))

Source

FOJ有奖月赛-2011年03月


组合数。

我的代码：
 1 #include <stdio.h>
 2 
 3 typedef  long  long  Lint;
 4 
 5 #define  L  203
 6 #define  MOD  1000000007
 7 
 8 int c[ L ][ L ];
 9 
10 int main() {
11         int n, m, i, j, ans;
12         for ( i = 0; i < L; ++i ) {
13                 c[ i ][ 0 ] = c[ i ][ i ] = 1;
14                 for ( j = 1; j < i; ++j ) {
15                         c[ i ][ j ] = ( c[ i - 1 ][ j - 1 ] + c[ i - 1 ][ j ] ) % MOD;
16                 }
17         }
18         while ( scanf( "%d%d", &n, &m ) == 2 ) {
19                 if ( m < 0 ) {
20                         ans = ( c[n+n-1][n] + (Lint)(MOD-c[(n-1)+(n-n/2-1)][n-1]) * n ) % MOD;
21                 }
22                 else {
23                         ans = c[ (n-1) + (n-n/2-1) ][ n-1 ];
24                 }
25                 printf( "%d\n", ans );
26         }
27         return 0;
28 }
29 

posted on 2011-03-23 22:46 coreBugZJ 阅读(1433) 评论(0)  编辑 收藏 引用 所属分类: ACM


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理