【杂题】[LibreOJ #6608] 无意识的石子堆【容斥原理】【FFT】

Description

Solution

943718401=225*2^22+1

显然每行必须有两个，我们不妨枚举有k列有2个石子，那么有2(n-k)列有1个石子。

\[Ans=\sum\limits_{k=0}^{n}{m\choose k}{m-k\choose 2(n-k)}S_k
\]

抽象一下问题，我们有n种颜色的球，每种颜色的球有两个且没有区别，现在要将它们放进k+2(n-k)个有区别的盒子中，其中k个盒子无序的放2个球，2(n-k)个盒子放1个球，同种颜色的球不能放入同一个盒子，\(S_k\)就是方案数，我们只需要快速算出所有的\(S_k\)。

同种颜色的球不能放入同一个盒子的限制比较烦人，我们考虑容斥。

枚举有多少个盒子放了两个相同颜色的球。

从n种颜色选出i个颜色，k个盒子选出i个盒子，以某种顺序放置。

我们先假定同种颜色的两个球不同，k个盒子的两个球有序，最后再除掉。

剩下(2n-2i)!个球再以某种顺序填入盒子。

那么有

\[S_k={1\over 2^{n+k}}\sum\limits_{i=0}^{k}{k\choose i}{n\choose i}i!(-1)^{i}2^i(2n-2i)!
\]

这是一个卷积的形式，可以用FFT加速。

这样就只用了一次卷积就算出了答案。

时间复杂度\(O(n\log n)\)

Code

#include <bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;++i)

#define fod(i,a,b) for(int i=a;i>=b;--i)

#define LL long long

using namespace std;

int M,L;

const int mo=943718401;

const int MAXM=4194304;

LL js[MAXM+1],ny[MAXM+1];

LL ksm(LL k,LL n)

{

	LL s=1;

	for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;

	return s;

}

namespace poly

{

	int wi[MAXM+1],bit[MAXM+1],ns;

	void init()

	{

		js[0]=1;

		fo(i,1,M) js[i]=js[i-1]*i%mo,bit[i]=(bit[i>>1]>>1)|((i&1)<<(L-1));

		ny[M]=ksm(js[M],mo-2);

		fod(i,M-1,0) ny[i]=ny[i+1]*(i+1)%mo;

		wi[0]=1;

		wi[1]=ksm(7,(mo-1)/M);

		fo(i,2,M) wi[i]=(LL)wi[i-1]*wi[1]%mo;

		ns=ksm(M,mo-2);

	}

	void DFT(int *a)

	{

		int v;

		fo(i,0,M-1) if(i<bit[i]) swap(a[i],a[bit[i]]);

		for(int h=1;h<M;h<<=1)

		{

			int wn=wi[M/h/2];

			for(int j=0;j<M;j+=h*2)

			{

				int *x=a+j,*y=x+h,w=1;

				for(int i=0;i<h;i++,x++,y++,w=(LL)w*wn%mo)

				{

					v=(LL)*y * w%mo;

					*y=(*x-v+mo)%mo;

					*x=(*x+v)%mo;

				}

			}

		}

	}

	void IDFT(int *a)

	{

		DFT(a);

		fo(i,0,M-1) a[i]=(LL)a[i]*ns%mo;

		reverse(a+1,a+M);

	}

}

using poly::init;

using poly::DFT;

using poly::IDFT;

LL n,m;

LL C(int n,int m)

{

	if(n<m) return 0;

	return js[n]*ny[m]%mo*ny[n-m]%mo;

}

int a[MAXM+1],b[MAXM+1];

int main()

{

	cin>>n>>m;

	M=1,L=0;

	while(M<2*n+2) M<<=1,L++;

	init();

	LL v=1;

	fo(i,0,n)

	{

		a[i]=v*C(n,i)%mo*js[2*(n-i)]%mo%mo;

		b[i]=ny[i]%mo;

		v=mo-v;

		v=v*2%mo;

	}

	DFT(a),DFT(b);

	fo(i,0,M-1) a[i]=(LL)a[i]*b[i]%mo;

	IDFT(a);

	LL ans=0,vs=1,ck=1,cn=1;

	fo(i,0,min(m-1,n*2-1)) cn=(m-i)%mo*js[i]%mo*ny[i+1]%mo*cn%mo;

	fo(i,0,n)

	{

		if(2*(n-i)<=m-i) ans=(ans+vs*ck%mo*cn%mo*a[i]%mo*js[i]%mo)%mo;

		vs=vs*ny[2]%mo;

		ck=(m-i)%mo*js[i]%mo*ny[i+1]%mo*ck%mo;

		if(2*(n-i)<=m-i) cn=cn*ksm((m-i)%mo*((m-2*n+i+1)%mo)%mo,mo-2)%mo*(((n-i)*2-1+mo)%mo*((n-i)*2%mo)%mo)%mo;

	}

	ans=ans*vs%mo*2%mo;

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

}

巴特西

【杂题】[LibreOJ #6608] 无意识的石子堆【容斥原理】【FFT】

Description

Solution

Code

最新文章

热门文章