正題

題目鏈接:https://www.luogu.com.cn/problem/P4640

---

題目大意

$n$種物品，其中$t$種物品是有個(gè)數(shù)限制的，第$i$種限制為$b_i$，求選出$m$個(gè)物品的方案數(shù)$\%p$的值
$1\le n,m,b_i\le 10^9,0\le t\le 15,p\in [1,10^5]\cap Pri$

---

解題思路

看上去就很$\text{OGF}$的題目？
對于有限制的物品為$f(x)=\frac{1?x^{b_i+1}}{1?x}$，其他都是$f(x)=\frac{1}{1?x}$。

然后$n$個(gè)乘起來的話然后求前$m$次項(xiàng)的系數(shù)。

分子因?yàn)橹挥?span id="ze8trgl8bvbq" class="katex--inline">$t$個(gè)有值，直接暴力乘起來。下面那個(gè)分母是$\frac{1}{(1?x{)}^n}$

所以對于上面如果有一個(gè)$a{x}^{m?k}$那么就會產(chǎn)生貢獻(xiàn)
$$a\sum _{i=0}^k\left(\genfrac{}{}{0ex}{}{n+i?1}{n}\right)=a\left(\genfrac{}{}{0ex}{}{n+k}{n}\right)$$
（相等于選出$0～k$個(gè)球放進(jìn)$n$個(gè)盒子里，開一個(gè)垃圾箱把沒用的球放進(jìn)去就好了）

然后模數(shù)小，開$Lucas$就好了

時(shí)間復(fù)雜度$O(2^t{\log }_{p}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; ll n,t,m,p,b[20],ans,inv[N],fac[N]; ll C(ll n,ll m) {return fac[n]*inv[m]%p*inv[n-m]%p;} ll L(ll n,ll m){if(n<m)return 0;if(n<p)return C(n,m);return L(n/p,m/p)*L(n%p,m%p)%p; } signed main() {scanf("%lld%lld%lld%lld",&n,&t,&m,&p);for(ll i=0;i<t;i++)scanf("%lld",&b[i]),b[i]++;inv[1]=1;for(ll i=2;i<p;i++)inv[i]=p-inv[p%i]*(p/i)%p;inv[0]=fac[0]=1;for(ll i=1;i<p;i++)fac[i]=fac[i-1]*i%p,inv[i]=inv[i-1]*inv[i]%p;ll MS=(1<<t); for(ll s=0;s<MS;s++){ll f=1,sum=0;for(ll i=0;i<t;i++)if((s>>i)&1)f=-f,sum+=b[i];(ans+=L(n+m-sum,n)*f)%=p;}printf("%lld\n",(ans+p)%p);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P4640-[BJWC2008]王之财宝【OGF,Lucas定理】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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