codeforces - E. Devu and Flowers & LightOJ 1124 Cricket Ranking(容斥定理+lucas定理)

时间：2022-12-18 22:09:36

E. Devu and Flowers(传送门)

time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Devu wants to decorate his garden with flowers. He has purchased n  boxes, where the i  -th box contains fi flowers. All flowers in a single box are of the same color (hence they are indistinguishable). Also, no two boxes have flowers of the same color.

Now Devu wants to select exactly s  flowers from the boxes to decorate his garden. Devu would like to know, in how many different ways can he select the flowers from each box? Since this number may be very large, he asks you to find the number modulo (10 9  + 7)  .

Devu considers two ways different if there is at least one box from which different number of flowers are selected in these two ways.

Input

The first line of input contains two space-separated integers n  and s(1 ≤ n ≤ 20,0 ≤ s ≤ 1014). 

The second line contains n  space-separated integers f 1 ,  f 2, ...f n (0 ≤ f i  ≤ 1012). 

Output

Output a single integer — the number of ways in which Devu can select the flowers modulo (10 9  + 7)  .

Examples

input

2 3
1 3

output

2

input

2 4
2 2

output

1

input

3 5
1 3 2

output

3

Note

Sample 1. There are two ways of selecting 3  flowers: {1, 2}  and {0, 3}  .

Sample 2. There is only one way of selecting 4  flowers: {2, 2}  .

Sample 3. There are three ways of selecting 5  flowers: {1, 2, 2}  , {0, 3, 2}  , and {1, 3, 1}  .

题意

给定 s  朵花，从 n  个花坛中选择花朵，第 i  花坛有 F[i]  朵花，每一个花坛中花都一样，不同花坛中花则不相同，求解有多少种组合方案可以构成 s  朵花

解题思路

可以用隔板法，针对超出花坛的部分进行隔板处理，然后用总的个数减去超出花坛数量的部分就是最终答案 [  隔板法是解决排列组合的一个非常重要的方法，如果读者不知道的话，可以学习一下，非常有用 ] 

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int MAXN = 2e1 + 5;
const int mod = 1e9 + 7;
LL F[MAXN];

LL mod_pow(LL x, LL n, LL mod){
    LL ret = 1;
while(n > 0){
if(n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
return ret;
}

LL C(LL m, LL n, LL p){
if(n < m) return 0;
if(m > n - m){
        m = n - m;
    }
    LL up = 1, down = 1;
for(LL i = 0;i < m;i ++){
        up = up * (n - i) % p;
        down = down * (i + 1) % p;
    }
return up * mod_pow(down, p - 2, p) % p;
}

LL lucas(LL m, LL n, LL p){
if(m == 0) return 1;
return C(m % p, n % p, p) * lucas(m / p, n / p, p) % p;
}

int n;
LL s;

LL solve(){
    LL ans = 0;
for(int i = 0;i < 1 << n;i ++){
int jo = 0;
        LL sum = s;
for(int j = 0;j < n;j ++){
if(i >> j & 1){
                jo ++;
sum -= F[j] + 1;
            }
        }
if(sum < 0) continue;
if(jo & 1){
            ans -= lucas(n - 1, sum + n - 1, mod);
        }
else{
            ans += lucas(n - 1, sum + n - 1, mod);
        }
        ans = (ans + mod) % mod;
    }
return (ans + mod) % mod;
}


int main(){
while(~scanf("%d%lld", &n, &s)){
for(int i = 0;i < n;i ++){
            scanf("%lld", &F[i]);
        }
        printf("%lld\n", solve());
    }
return 0;
}

Cricket Ranking(传送门)

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Submit
Status
Practice
LightOJ 1124
uDebug

Description

World Cup Cricket 2011 is coming. Many of you may not be interested in cricket, but it’s really a passion in our subcontinent. Ranking of cricketers is a common phenomenon there. Cricketers are ranked by their performance in both form of cricket (Test and One-day). People really enjoy this ranking. They like to see their favorite players as top ranked. Currently many such rankings are available. And as you have guessed, each ranking makes a different player as top ranked.

World Cup committee has decided that they will make a new ranking on the performance of players in the world cup. They want the ranking to be acceptable to the public. The rules are:

1) There are K different departments. Cricketers will be given points in each department depending on their performance.
2) The maximum points for each department are not equal. Such as Sakib Al Hasan can get maximum 25 points in batting but Mushfiqur Rahim can get maximum 10 points for his spectacular wicket keeping.
3) The sum of maximum points of all departments will be exactly N points. And the final ranking will depend on the total earned points out of N points.

The ranking committee wants popular cricketers to get top ranked. To do so, they even allow maximum points for fielding more than that of batting. But that can bring lots of criticism. So they decide to fix a range of points for each department. Such as maximum points for batting will be at least 10 and at most 15 or for fielding, it will be at least 8 and at most 12. But the total points will be 20. Then 3 ranking systems are possible, such as: (10, 10), (11, 9) and (12, 8) for batting and fielding respectively. In this problem, you have to find the number of ranking systems possible for given number of departments, range of points for each department and total points.

Input

Input starts with an integer T(≤100)  , denoting the number of test cases.

Each case starts with a blank line and two integers K(1≤K≤10)  and N(1≤N≤10 6 )  . Each of the next K lines denotes the lower and upper limit of allowable maximum points for each department. These integers will be in the range [0,106]  . And the lower limit of each department will always be less than or equal to the upper limit of that department.

Output

For each case, print the case number and the number of rankings possible modulo 100000007.

Sample Input

4

4 10
1 1
2 2
3 3
4 4

4 10
1 1
2 2
3 3
3 3

2 10
1 10
1 10

2 20
10 15
8 12

Sample Output

Case 1: 1
Case 2: 0
Case 3: 9
Case 4: 3

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int MAXN = 10 + 5;
const int mod = 1e8 + 7;

struct Depart{
int l, r;
}D[MAXN];


int T, K;
LL N;

LL mod_pow(LL x, LL n, LL p){
    LL ret = 1;
while(n){
if(n & 1) ret = ret * x % p;
        x = x * x % p;
        n >>= 1;
    }
return ret;
}

LL C(LL m, LL n, LL p){
if(n < m) return 0;
if(m > n - m){
        m = n - m;
    }
    LL up = 1, down = 1;
for(LL i = 0;i < m;i ++){
        up = up * (n - i) % p;
        down = down * (i + 1) % p;
    }
return up * mod_pow(down, p - 2, p) % p;
}

LL lucas(LL m, LL n, LL p){
if(m == 0) return 1;
return C(m % p, n % p, p) * lucas(m / p, n / p, p) % p;
}

LL solve(){
    LL ans = 0;
for(int i = 0;i < 1 << K;i ++){
int oj = 0;
        LL s = N;
for(int j = 0;j < K;j ++){
if(i >> j & 1){
                oj ++;
                s -= D[j].r - D[j].l + 1;
            }
        }
if(s < 0) continue;
if(oj & 1){
            ans -= lucas(K - 1, s + K - 1, mod);
        }
else{
            ans += lucas(K - 1, s + K - 1, mod);
        }
        ans %= mod;
    }
return (ans + mod) % mod;
}


int main(){
int cas = 1;
scanf("%d", &T);
while(T --){
scanf("%d%lld", &K, &N);
for(int i = 0;i < K;i ++){
scanf("%d%d", &D[i].l, &D[i].r);
            N -= D[i].l;
        };
printf("Case %d: %lld\n",cas ++, solve());
    }
return 0;
}
标签：

相关文章