codeforces Lightsabers (hard)

题目大意：

给定每种球的数量，求从中选取k个球有多少种不同的取法，同种球视为相同的。

题解：

多项式(1+x+x^2+...+x^a[1])*(1+x+x^2+...+x^a[2])*(1+x+x^2+...+x^a[3])*...*(1+x+x^2+...+x^a[n])的第k次项的系数。

首先我们注意到模数，1009，问了人发现这东西没有原根。然后开始贴分治NTT+中国剩余定理模板。交了无数次WA后发现T了......cf居然开始卡常了。

有人说MTT......然而不会。真的无奈，不知道怎么办。akteam成功的掉出了第一页，然后差点掉出第二页。

结束以后开始翻别人ac代码。FFT.......做完一遍转成int模一下.........没话说，怪不得模数这么小.......

代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<complex>

using namespace std;

#define pi acos(-1)

const int mod=1009;

int ssum[2000005],x[2000005],anss[2000005],mi[2000005],ni[2000005],S[2000005];

int p,T,n,m,R[1000010];

typedef complex<double> E;

struct node2

{

	E num[10000010];

	int now;

};

namespace task2

{

	int len,L;

	long long solux,soluy;

	node2 LAST;

	E a[1000010],b[1000010];

	inline void NTT(E *a,int flag){

		for (int i=0;i<n;i++)

			if (i<R[i]) swap(a[i],a[R[i]]);

		for (int i=1;i<n;i<<=1){

			E wn(cos(pi/i),flag*sin(pi/i));

			for (int j=0;j<n;j+=(i<<1)){

				E w(1,0);

				for (int k=0;k<i;k++,w*=wn){

					E x=a[j+k],y=a[j+k+i]*w;

					a[j+k]=x+y;a[j+k+i]=x-y;

				}

			}

		}

		if (flag==-1) for (int i=0; i<n; i++) a[i]=a[i]/(E)n;

	}

	int Solve(int l,int r)

	{

		if (l==r)

		{

			int st=LAST.now+1;

			for (int i=0; i<=anss[l]; i++)

				LAST.num[++LAST.now]=1;

			return st;

		}

		int mid=(l+r)>>1;

		int A=Solve(l,mid);

		int B=Solve(mid+1,r);

		n=ssum[mid]-ssum[l-1],m=ssum[r]-ssum[mid];

		m+=n;L=0;

		for (n=1;n<=m;n<<=1) L++;

		for (int i=0;i<n;i++) R[i]=((R[i>>1]>>1)|((i&1)<<(L-1)));

		for (int i=0;i<=ssum[mid]-ssum[l-1];i++) a[i]=LAST.num[A+i];

		for (int i=0;i<=ssum[r]-ssum[mid];i++) b[i]=LAST.num[B+i];

		for (int i=ssum[mid]-ssum[l-1]+1;i<n;i++) a[i]=0;

		for (int i=ssum[r]-ssum[mid]+1;i<n;i++) b[i]=0;

		NTT(a,1);NTT(b,1);

		for (int i=0;i<n;i++) a[i]=a[i]*b[i];

		NTT(a,-1);

		int st=LAST.now+1;

		for (int i=0;i<=m;i++)

			LAST.num[++LAST.now]=((long long)(a[i].real()+0.5))%mod;

		return st;

	}

	void solve()

	{

		int n,m,k;

		scanf("%d%d%d",&n,&m,&k);

		for (int i=1; i<=n; i++){

			scanf("%d",&x[i]);

			S[x[i]]++;

		}

		int cnt=0;

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

			if (S[x[i]]){

				anss[++cnt]=S[x[i]];

				S[x[i]]=0;

			}

		for (int i=1; i<=cnt; i++)

			ssum[i]=ssum[i-1]+anss[i];

		LAST.now=0;

		int xis=Solve(1,cnt);

		printf("%d\n",(int)(LAST.num[xis+k].real()+0.1));

	}

}

int main()

{

	task2::solve();

	return 0;

}

巴特西

codeforces Lightsabers (hard)

最新文章

热门文章