正题

题目链接:https://www.luogu.com.cn/problem/P4640

题目大意

\(n\)种物品，其中\(t\)种物品是有个数限制的，第\(i\)种限制为\(b_i\)，求选出\(m\)个物品的方案数\(\% p\)的值

\(1\leq n,m,b_i\leq 10^9,0\leq t\leq 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\)个乘起来的话然后求前\(m\)次项的系数。

分子因为只有\(t\)个有值，直接暴力乘起来。下面那个分母是\(\frac{1}{(1-x)^n}\)

所以对于上面如果有一个\(ax^{m-k}\)那么就会产生贡献

\[a\sum_{i=0}^{k}\binom{n+i-1}{n}=a\binom{n+k}{n}
\]

（相等于选出\(0\sim k\)个球放进\(n\)个盒子里，开一个垃圾箱把没用的球放进去就好了）

然后模数小，开\(Lucas\)就好了

时间复杂度\(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;

}

巴特西

P4640-[BJWC2008]王之财宝【OGF,Lucas定理】

正题

题目大意

解题思路

code

最新文章

热门文章