正題

題目鏈接:https://www.luogu.org/problem/CF451E

---

題目大意

長度為$n$的序列$a_i$，有如下要求

$a_i\in [0...x_i]$

${\sum }_{i=1}^n{a}_i=s$

求序列個數(shù)。

---

解題思路

考慮容斥，這樣我們就可以將條件轉(zhuǎn)換為$a_i>x_i$，然后我們可以讓$n?x_i?1$這樣就將條件變?yōu)榱?span id="ze8trgl8bvbq" class="katex--inline">$a_i\ge 0$，然后可以用組合數(shù)插板法計算，也就是答案為
$$\sum _S{C}_{s?{\sum }_{x_i\in S}(x_i+1)?1}^{n?1}?(?1{)}^{|S|}$$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll XJQ=1e9+7; ll n,s,inv[50],x[50],ans; bool v[50]; ll power(ll x,ll b) {ll ans=1;while(b){if(b&1) ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } ll C(ll n,ll m) {if(n<0||m<0||n<m)return 0;if(n%XJQ==0||m==0)return 1;ll x=1;for(ll i=n-m+1;i<=n;i++)x=x*(i%XJQ)%XJQ;return x*inv[m]%XJQ; } void dfs(ll dep,ll _,bool flag) {ll _n=s+n;for(ll i=1;i<=n;i++)if(v[i]) _n-=x[i]+1;if(flag)ans=((ans+_*C(_n-1,n-1))%XJQ+XJQ)%XJQ;if(dep>n) return;v[dep]=1;dfs(dep+1,-_,1);v[dep]=0;dfs(dep+1,_,0); } int main() {scanf("%lld%lld",&n,&s);inv[1]=1;for(ll i=2;i<=20;i++)inv[i]=inv[i-1]*power(i,XJQ-2)%XJQ;for(ll i=1;i<=n;i++)scanf("%lld",&x[i]);ans=C(s+n-1,n-1);dfs(1,1,0);printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的CF451E-Devu and Flowers【组合计数,容斥】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。