原文链接https://www.cnblogs.com/zhouzhendong/p/UOJ424.html

题解

主席太神仙了！

首先我们把题意转化成：对所有挺好序列建笛卡尔树，有多少笛卡尔树互不同构。

容易推出 dp 式子：$f[i][j]$ 表示 $j$ 个数，他们的 max 为 i 。

$$f[i][j] = \sum_{k=0}^{j-1} f[i-1][k] * f[i][j-k-1]\\f[i][0] = 1\\f[0][i] = 0(i>0)\\f[1][i] = 1$$

这里注意一下：设当前的max为 v，左侧区间的max为 maxL，右侧为 maxR，那么由于每次是取区间最大值的最靠左下标，所以 maxL<v，而 maxR<=v 。

先不考虑每 1...m 每一个数都要出现。

可以发现，如果 maxL<v-1 ，那么只要将左子树的所有节点都加上 v-1-MaxL ，那么 maxL<v-1 的任意一种情况都可以在 maxL=v-1 时的所有情况中找到同构的情况。

右侧也类似。

所以左侧只往 i-1转移，右侧只往 i 转移。这样本身显然是没有同构了。

现在考虑 1...m 每一个数都要出现。

显然如果 n<m 那么答案为 0 。

否则，显然 1...m 不用全部出现的情况下的所有笛卡尔树构成的集合（设为 S1）包含了 1...m 全部出现的情况下的所有笛卡尔树构成的集合（设为 S2）。

接下来我们来说明一下 S1 的每一种笛卡尔树都与 S2 的一种笛卡尔树对应。

如果 S1 中的一棵笛卡尔树本来就包含了 1...m ，那么直接对应即可。

如果 S1 中的一棵笛卡尔树少包含了一些，那么由于 n>=m ，一定可以在不改变笛卡尔树的同时调节节点权值使得 1..m 都出现，于是也可以对应 S2 中的一种笛卡尔树。

由于 S1 中的任意两个笛卡尔树互不同构，所以 S1 与 S2 的元素一一对应，也就是说 |S1|=|S2| 。

于是我们要求的就是 $f[m][n]$ 。

设多项式 $f_i(x)$ 满足 $f_i(x)[j]=f[i][j]$ ，那么我们可以得到递推式：

$$f_i(x) = x f_{i-1}(x)f_i(x) + 1\\f_i(x) = \frac{1}{1-xf_{i-1}(x)}$$

这个式子很棘手。

我们把他表示成 $\frac{A_i(x)}{B_i(x)}$ 的形式，再推一推：

$$\frac{A_i(x)}{B_i(x)} = \frac 1 {1-x\frac{A_{i-1}(x)}{B_{i-1}(x)}}\\=\frac{B_{i-1}(x)}{B_{i-1}(x) - xA_{i-1}(x) }$$

于是我们可以得到线性递推式：

$$A_i(x) = B_{i-1}(x)$$

$$B_i(x) = B_{i-1}(x) - xA_{i-1}(x)$$

于是我们可以得到：

$$\begin{bmatrix}0 & 1\\-x & 1 \end{bmatrix}\begin{pmatrix}A_{i-1}(x)\\B_{i-1}(x)\end{pmatrix}=\begin{pmatrix}A_i(x)\\B_i(x)\end{pmatrix}$$

其中 $A_0(x) = B_0(x) = 1$ 。

直接暴力把多项式当做矩阵中的元素，复杂度 $O(n\log ^2 n)$ 。

直接把单位根代入，直接得到 $A_m(x)$ 和 $B_m(x)$ 的点值，最后 DFT 回来。时间复杂度 $O(n\log n)$ 。

还要写个多项式求逆。

所以总时间复杂度 $O(n\log n )$ 。

好像有个 $O(n)$ 的神仙做法。不会。告辞。

代码

#pragma GCC optimize("Ofast","inline")

#include <bits/stdc++.h>

#define clr(x) memset(x,0,sizeof (x))

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

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

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define _SEED_ ('C'+'L'+'Y'+'A'+'K'+'I'+'O'+'I')

#define outval(x) printf(#x" = %d\n",x)

#define outvec(x) printf("vec "#x" = ");for (auto _v : x)printf("%d ",_v);puts("")

#define outtag(x) puts("----------"#x"----------")

#define outarr(a,L,R) printf(#a"[%d...%d] = ",L,R);\

						For(_v2,L,R)printf("%d ",a[_v2]);puts("");

using namespace std;

typedef long long LL;

LL read(){

	LL x=0,f=0;

	char ch=getchar();

	while (!isdigit(ch))

		f|=ch=='-',ch=getchar();

	while (isdigit(ch))

		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

	return f?-x:x;

}

const int N=1<<20,mod=998244353;

void Add(int &x,int y){

	if ((x+=y)>=mod)

		x-=mod;

}

void Del(int &x,int y){

	if ((x-=y)<0)

		x+=mod;

}

int Pow(int x,int y){

	int ans=1;

	for (;y;y>>=1,x=(LL)x*x%mod)

		if (y&1)

			ans=(LL)ans*x%mod;

	return ans;

}

namespace poly{

	int w[N],R[N];

	int a[N],b[N];

	void prework(int n,int d){

		For(i,0,n-1)

			R[i]=(R[i>>1]>>1)|((i&1)<<(d-1));

		w[0]=1,w[1]=Pow(3,(mod-1)/n);

		For(i,2,n-1)

			w[i]=(LL)w[i-1]*w[1]%mod;

	}

	void FFT(int a[],int n){

		For(i,0,n-1)

			if (i<R[i])

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

		for (int t=n>>1,d=1;d<n;d<<=1,t>>=1)

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

				for (int j=0;j<d;j++){

					int tmp=(LL)w[t*j]*a[i+j+d]%mod;

					a[i+j+d]=(a[i+j]-tmp+mod)%mod;

					Add(a[i+j],tmp);

				}

	}

	vector <int> Mul(vector <int> A,vector <int> B){

		static vector <int> ans;

		ans.clear();

		int n,d;

		for (n=1,d=0;n<A.size()+B.size();n<<=1,d++);

		prework(n,d);

		For(i,0,n-1)

			a[i]=b[i]=0;

		For(i,0,(int)A.size()-1)

			a[i]=A[i];

		For(i,0,(int)B.size()-1)

			b[i]=B[i];

		FFT(a,n),FFT(b,n);

		For(i,0,n-1)

			a[i]=(LL)a[i]*b[i]%mod;

		w[1]=Pow(w[1],mod-2);

		For(i,2,n-1)

			w[i]=(LL)w[i-1]*w[1]%mod;

		FFT(a,n);

		int inv=Pow(n,mod-2);

		For(i,0,n-1)

			ans.pb((LL)a[i]*inv%mod);

		while (!ans.empty()&&!ans.back())

			ans.pop_back();

		return ans;

	}

	vector <int> Get_Inv(vector <int> a,int n){

		static vector <int> A,B,tmp;

		A.clear(),B.clear();

		B.pb(Pow(a[0],mod-2));

		for (int d=1;d<=n*2;d<<=1){

			while (A.size()<=d)

				if (a.size()>d)

					A.pb(a[A.size()]);

				else

					A.pb(0);

			tmp=Mul(A,Mul(B,B));

			tmp.resize(d+1,0);

			B.resize(d+1,0);

			For(i,0,d)

				B[i]=(2LL*B[i]-tmp[i]+mod)%mod;

		}

		B.resize(n+1,0);

		return B;

	}

}

using poly::FFT;

using poly::Mul;

using poly::Get_Inv;

struct Mat{

	int v[2][2];

	Mat(){}

	Mat(int x){

		clr(v);

		For(i,0,1)

			v[i][i]=x;

	}

	Mat(int v00,int v01,int v10,int v11){

		v[0][0]=v00,v[0][1]=v01;

		v[1][0]=v10,v[1][1]=v11;

	}

	friend Mat operator * (Mat A,Mat B){

		Mat ans(0);

		For(i,0,1)

			For(j,0,1)

				For(k,0,1)

					ans.v[i][j]=((LL)A.v[i][k]*B.v[k][j]+ans.v[i][j])%mod;

		return ans;

	}

};

Mat Pow(Mat x,int y){

	Mat ans(1);

	for (;y;y>>=1,x=x*x)

		if (y&1)

			ans=ans*x;

	return ans;

}

int n,m;

int k,d;

int a[N],b[N];

vector <int> A,B;

int solve(int n,int m){

	if (n<m)

		return 0;

	for (k=1,d=0;k<=n;k<<=1,d++);

	poly::prework(k,d);

	For(i,0,k-1){

		Mat res=Pow(Mat(0,1,(mod-poly::w[i])%mod,1),m)*Mat(1,0,1,0);

		a[i]=res.v[0][0],b[i]=res.v[1][0];

	}

	poly::w[1]=Pow(poly::w[1],mod-2);

	For(i,2,k-1)

		poly::w[i]=(LL)poly::w[i-1]*poly::w[1]%mod;

	FFT(a,k),FFT(b,k);

	A.clear(),B.clear();

	For(i,0,n)

		A.pb(a[i]),B.pb(b[i]);

	A=Mul(A,Get_Inv(B,n));

	A.resize(n+1,0);

	return A[n];

}

int main(){

	n=read(),m=read();

	cout<<solve(n,m)<<endl;

	return 0;

}

巴特西

UOJ#424. 【集训队作业2018】count 多项式,FFT,矩阵

题解

代码

最新文章

热门文章