正題

題目鏈接:http://noip.ybtoj.com.cn/contest/102/problem/1

---

題目大意

$n$個$x_i$在$[l_i,r_i]$中隨機選擇，給出一個$c$，一個序列$\sum k_i=c$
每種方案貢獻為$$\prod _{i=1}^n{x}_i^{k_i}$$

---

解題思路

設$f_{i,j}$表示到第$i$個小朋友，$c$已經分配了$j$出去時的貢獻和
$$f_{i,j}=\sum _{k=0}^j(f_{i,k}+\sum _{z=l_i}^{r_i}{z}^{j?k})$$

然后預處理后面那個東西的前綴和即可，時間復雜度$O(n{c}^2)$

---

解題思路

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=410,XJQ=1e9+7; ll n,c,l[N],r[N],f[N][N],z[N][N],ans; signed main() {freopen("candy.in","r",stdin);freopen("candy.out","w",stdout);scanf("%lld%lld",&n,&c);for(ll i=1;i<=n;i++)scanf("%lld",&l[i]);for(ll i=1;i<=n;i++)scanf("%lld",&r[i]);for(ll i=1;i<=400;i++){z[i][0]=1;for(ll j=1;j<=400;j++)z[i][j]=z[i][j-1]*i%XJQ;}for(ll i=0;i<=400;i++)for(ll j=1;j<=400;j++)(z[j][i]+=z[j-1][i])%=XJQ;f[0][0]=1;for(ll i=1;i<=n;i++)for(ll j=0;j<=c;j++)for(ll k=j;k<=c;k++)(f[i][k]+=f[i-1][j]*(z[r[i]][k-j]-z[l[i]-1][k-j])%XJQ)%=XJQ;printf("%lld",(f[n][c]+XJQ)%XJQ); }

總結

以上是生活随笔為你收集整理的YbtOJ#20067-[NOIP2020模拟赛B组Day5]糖果分配【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。