Codeforces Round #258 (Div. 2) E. Devu and Flowers 隔板法,容斥, Lucas

    xiaoxiao2021-03-25  299

    题目链接:http://codeforces.com/contest/451/problem/E 题意:有n个盒子,然后每个盒子有f[i]个,你需要拿出来s个球,问你一共有多少种选择。 解法:2^ n的状态,枚举说那些花坛的花取超过了,剩下的用C(n−1,sum+n−1)隔板法计算个数,注意奇数的位置要用减的,偶数的位置用加的,容斥原理。

    //CF 451E #include <bits/stdc++.h> using namespace std; const long long mod = 1e9+7; long long qmod(long long a, long long n) { long long res = 1; while(n){ if(n&1) res = res*a%mod; a = a*a%mod; n >>= 1; } return res; } long long C(long long a, long long b) { if(a < b) return 0; if(b > a - b) b = a - b; long long up = 1, down = 1; for(long long i = 0; i < b; i++){ up = up*(a-i)%mod; down = down*(i+1)%mod; } return up*qmod(down, mod-2)%mod; } long long lucas(long long a, long long b){ if(b == 0) return 1; return C(a%mod, b%mod)*lucas(a/mod, b/mod)%mod; } long long s, f[25]; int n; long long gao() { long long ans = 0; for(int i = 0; i < (1<<n); i++){ long long sgn = 1, sum = s; for(int j = 0; j < n; j++){ if(i&(1<<j)){ sum -= f[j]+1; sgn*=-1; } } if(sum < 0) continue; ans += sgn*lucas(sum+n-1, n-1)%mod; ans%=mod; } return (ans+mod)%mod; } int main() { scanf("%d%lld", &n, &s); for(int i = 0; i < n; i++) scanf("%lld", &f[i]); printf("%lld\n", gao()); return 0; }
    转载请注明原文地址: https://ju.6miu.com/read-49.html

    最新回复(0)