正題

題目鏈接:http://10.156.31.134/contestnew.aspx?cid=189

---

題目大意

$n$種物品，每種$a_i$個(gè)。放進(jìn)$k$個(gè)有序盒子求方案數(shù)（可以不放完）

---

解題思路

不放完其實(shí)就是$k+1$個(gè)盒子，插板法求$C_{k+a_i}^{a_i}$，即使$k$很大但是$a_i$很小，預(yù)處理即可

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll XJQ=998244353; ll n,k,f[110]; ll power(ll x,ll b){x%=XJQ;ll ans=1;while(b){if(b&1)ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } int main() {scanf("%lld%lld",&n,&k);ll z=1,inv=1;f[0]=1;for(ll i=1;i<=100;i++){z=z*((k+i)%XJQ)%XJQ;inv=inv*power(i,XJQ-2)%XJQ;f[i]=z*inv%XJQ;}ll ans=1;for(ll i=1;i<=n;i++){ll x;scanf("%lld",&x);ans=ans*f[x]%XJQ;}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的nssl1519-背包签到题【数论】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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