首页 > 代码库 > Codeforces Round #258 E Devu and Flowers --容斥原理
Codeforces Round #258 E Devu and Flowers --容斥原理
这题又是容斥原理，最近各种做容斥原理啊。当然，好像题解给的不是容斥原理的方法，而是用到Lucas定理好像。这里只讲容斥的做法。
题意：从n个容器中总共取s朵花出来，问有多少种情况。其中告诉你每个盒子中有多少朵花。
分析：其实就是求方程: x1+x2+...+xn = s 的整数解的个数，方程满足： 0<=x1<=a[1], 0<=x2<=a[2]...
设：A1 = {x1 >= a[1]+1} , A2 = {x2 >= a[2]+1} , .... , An = {xn >= a[n]+1}. 全集S = (n+s-1,s)
所以容斥原理可求得答案。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define Mod 1000000007#define lll __int64#define ll long longusing namespace std;#define N 100007ll a[22];ll inv[30];ll fastm(ll a,ll b){ ll res = 1LL; while(b) { if(b&1LL) res = (res*a)%Mod; b >>= 1; a = (a*a)%Mod; } return res;}ll comb(ll n,ll r){ if(r > n) return 0; r = min(r,n-r); n%=Mod; ll ans = 1LL; for(int i=0;i<=r-1;i++) { ans = ans*(n-i)%Mod; ans = ans*inv[i+1]%Mod; } return ans;}int calc(int s){ int cnt = 0; while(s) { if(s&1) cnt++; s >>= 1; } return cnt;}int main(){ int n,i; ll s; for(i=1;i<=30;i++) inv[i] = fastm(i,Mod-2); while(cin>>n>>s) { for(i=0;i<n;i++) cin>>a[i]; ll ans = 0; int S = (1<<n)-1; for(int state=0;state<=S;state++) { ll r = s; int tmp = state; int cnt = calc(state); i=0; while(i<n) { if(tmp&1) r -= (a[i]+1); tmp >>= 1; i++; } if(r < 0) continue; ll cb = comb(n+r-1,r); if(cnt%2) cb = -cb; ans = (ans+cb+Mod)%Mod; } printf("%I64d\n",ans); } return 0;}
Codeforces Round #258 E Devu and Flowers --容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。