LOJ #6051. 「雅礼集训 2017 Day11」PATH

完了感觉最近留了好多坑的说，这题也是模模糊糊地会一点

首先我们发现题目要求的是单调不上升的序列个数，那么一个套路就是用值减去下标

然后考虑连续位置的限制，这个我们做一个置换然后尽量向后取

这样拿值和位置卷积就变成了合法方案数的分子\(\times\)总方案数的分母？

感觉策不太懂啊，QQ上加了一个dalao问下细节，具体的到时候来填吧

先把CODE放了

#include<cstdio>

#include<cctype>

#define RI register int

#define CI const int&

#define Tp template <typename T>

using namespace std;

const int N=500005,mod=1004535809;

int n,m,len,lim,a[N],b[N],fact[N],F[N<<3],G[N<<3],ans;

class FileInputOutput

{

	private:

		static const int S=1<<21;

		#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,S,stdin),A==B)?EOF:*A++)

		char Fin[S],*A,*B;

	public:

		Tp inline void read(T& x)

		{

			x=0; char ch; while (!isdigit(ch=tc()));

			while (x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));

		}

		#undef tc

}File;

inline void maxer(int& x,CI y)

{

	if (y>x) x=y;

}

inline int quick_pow(int x,int p=mod-2,int mul=1)

{

	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;

}

class Poly_solver

{

	private:

		int rev[N<<3],p;

		inline void swap(int& x,int& y)

		{

			int t=x; x=y; y=t;

		}

		inline int sum(CI a,CI b)

		{

			int t=a+b; return t>=mod?t-mod:t;

		}

		inline int sub(CI a,CI b)

		{

			int t=a-b; return t<0?t+mod:t;

		}

	public:

		inline void init(CI n)

		{

			for (lim=1,p=0;lim<=n;lim<<=1,++p);

			for (RI i=0;i<lim;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<p-1);

		}

		inline void NTT(int *f,CI opt)

		{

			RI i; for (i=0;i<lim;++i) if (i<rev[i]) swap(f[i],f[rev[i]]);

			for (i=1;i<lim;i<<=1)

			{

				int m=i<<1,D=quick_pow(3,~opt?(mod-1)/m:mod-1-(mod-1)/m);

				for (RI j=0;j<lim;j+=m)

				{

					int W=1; for (RI k=0;k<i;++k,W=1LL*W*D%mod)

					{

						int x=f[j+k],y=1LL*f[i+j+k]*W%mod;

						f[j+k]=sum(x,y); f[i+j+k]=sub(x,y);

					}

				}

			}

			if (!~opt)

			{

				int Inv=quick_pow(lim); for (i=0;i<lim;++i) f[i]=1LL*f[i]*Inv%mod;

			}

		}

}P;

int main()

{

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	RI i; for (File.read(n),i=1;i<=n;++i)

	File.read(a[i]),b[a[i]]=i,++F[a[i]-i+n];

	for (i=m=a[1];i;--i) maxer(b[i],b[i+1]),++G[b[i]-i+m];

	for (P.init((len=n+m)<<1),P.NTT(F,1),P.NTT(G,1),i=0;i<lim;++i)

	F[i]=1LL*F[i]*G[i]%mod; for (P.NTT(F,-1),i=ans=1;i<=len;++i)

	ans=1LL*ans*quick_pow(i,F[i-1+n+m])%mod; ans=quick_pow(ans);

	for (fact[0]=i=1;i<=m;++i) fact[i]=1LL*fact[i-1]*i%mod;

	for (i=1;i<=n;++i) ans=1LL*ans*fact[a[i]]%mod;

	return printf("%d",ans),0;

}

巴特西

LOJ #6051. 「雅礼集训 2017 Day11」PATH

最新文章

热门文章