hdu 5201 The Monkey King【容斥原理+组合数学】

原来我一开始以为的\( O(n^2) \)是调和级数\( O(nlog_2n) \)的！

首先枚举猴王的桃子个数\( x \)，然后使用容斥原理，枚举有至少\( k \)个不满足的条件，那么这\( k \)个不满足的条件得组合个数为\( C_{m-1}^{k} \)，这\( k \)个不满足的条件每个至少是\( x+1 \)，在总的桃子个数中去掉不满足条件的\( k \)个\( x+1 \)，然后在剩下的桃子中使用隔板法，方案数为\( C_{n-(k+1)*x+m-2}^{m-2} \)

那么就可以得到公式：

\[ans=\sum_{x=1}^{x<=n,x>\frac{n-x}{m-1}}(\sum_{k=0}^{n-(k+1)*x\geq 0}((-1)^k*C_{m-1}^{k}*C_{n-(k+1)*x+m-2}^{m-2}))
\]

关于这个的复杂度呢看似平方实则是调和级数\( O(nlog_2n) \)的……但是我不太会算啊据说内层的k一共有n/x种取值

#include<iostream>

#include<cstdio>

using namespace std;

const long long N=200005,mod=1e9+7;

long long T,n,m,inv[N],fac[N],ans;

long long ksm(long long a,long long b)

{

	long long r=1ll;

	while(b)

	{

		if(b&1)

			r=r*a%mod;

		a=a*a%mod;

		b>>=1;

	}

	return r;

}

long long C(long long n,long long m)

{

	return fac[n]*inv[n-m]%mod*inv[m]%mod;

}

int main()

{

	fac[0]=1;

	for(int i=1;i<=N-5;i++)

		fac[i]=fac[i-1]*i%mod;

	inv[N-5]=ksm(fac[N-5],mod-2);

	for(int i=N-6;i>=0;i--)

		inv[i]=inv[i+1]*(i+1)%mod;

	scanf("%lld",&T);

	while(T--)

	{

		scanf("%lld%lld",&n,&m);

		if(m==1||n==1)

		{

			puts("1");

			continue;

		}

		ans=0ll;

		for(int x=1;x<=n;x++)

			if(x>(n-x)/(m-1))

				for(int k=0;n-(k+1)*x>=0;k++)

					ans=(ans+((k&1)?-1:1)*C(m-1,k)*C(n-(k+1)*x+m-2,m-2))%mod;

		printf("%lld\n",(ans%mod+mod)%mod);

	}

	return 0;

}

巴特西

hdu 5201 The Monkey King【容斥原理+组合数学】

最新文章

热门文章