UOJ#424. count

发表于 | 分类于

题目描述

如果一个序列满足序列长度为 $n$，序列中的每个数都是 $1$ 到 $m$ 内的整数，且所有 $1$ 到 $m$ 内的整数都在序列中出现过，则称这是一个挺好序列。

对于一个序列 $A$，记 $f_A(l,r)$ 为 $A$ 的第 $l$ 个到第 $r$ 个数中最大值的下标（如果有多个最大值，取下标最小的）。

两个序列 $A$ 和 $B$ 同构，当且仅当 $A$ 和 $B$ 长度相等，且对于任意 $i≤j$ ，均有 $f_A(i,j)=f_B(i,j)$ 。

给出 $n,m$ ，求有多少种不同构的挺好序列。答案对 $998244353$ 取模。

输入格式

一行两个正整数 $n,m$ 。

输出格式

一行一个整数，表示有多少种不同构的挺好序列。

输入输出样例

input

1
3 2

output

1
4

数据范围

$n,m\le 10^5$

题解

首先我们定义一个序列所对应的$g$序列：$g[i]$为使 $a[g[i]]>a[i]$ 且 $g[i]>i$的最小值，如不存在则为$n+1$

很显然对于$a,b$序列，它们所对应的$g$序列如果对于 $\forall_i,g_a[i]=g_b[i]$，则$a,b$序列一定同构

现在问题就转化为了所有合法的$g$序列中，有哪些序列能刚好被涂$m$种颜色

一个$g$序列是合法的，需要满足$\forall{i\le j},g[i]>=g[j]$，相当于如果把它看成线段，那么没有交错的线段

很显然只要$n\ge m$，就不会出现剩下颜色的情况。我们接下来考虑颜色不够的这种不合法情况，如果把$g$序列当做一棵有根树，只要树的最大深度不超过$m$，序列就能被刚好涂$m$种颜色，很显然满足必要性。充分性证明如下：

上面条件是对它的颜色严格大于进行这种类约束，需证明严格小于不会对最大深度造成影响。设$x,y$，$x < y$且因$g$序列造成只能 $a[y]<a[x]$ 的限制。首先一定满足 $x<y<g[x]$ ，不然 $a[x]$ 不会对 $a[y]$ 造成限制，其次要求$g[y]<g[x]$，否则它可以构造出$a[x]=a[y]$的替代情况。如果将$y$添加到$x$与树上的儿子，且树的最大深度增加的话，那$x$一定不位于原$root \rightarrow maxdeep$的链上。因为$a[g[y]]\le a[g[x]]$，所以$dis(y,g[x])\ge 2 \ge dis(x,g[x])$，当前情况$x\not=maxdeep$

那么只要构造的$g$序列合法且$maxdeep\le m$就能被计数

考虑倒序构造$g$序列，假设现在正在构造 $g[i]$，相当于在树上插入叶子节点$i$，很显然 $g[i]$只能为$i+1$或$i+1$的祖先节点。这个操作可以拆成 跳父亲 和 插入叶子节点并移到叶子节点 这两个操作，对应弹栈和入栈。

那么现在问题就转化为了一个变种的卡特兰数：$c[i]=1\ or\ -1，\forall{i}, 0\le c_{suf}[i]\le m$

现在就可以直接上多项式了qwq

考虑容斥，任意一次操作(包括不合法的)权值为它在上下界交错打破了多少次(如果x算突破上界，y算突破下界，abaab的权值为4)。你现在要求出权值为零的操作次数，如果$v[x][0/1]​$表示权值至少为$x​$且第一次是突破上界/下界的操作数。求 $\sum_{i=0}^{2*n} {-1^{i} \times (v[i][0]+v[i][1])}​$

$v$函数可以通过多次折射求出

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll jc[202020],jc_ny[202020];
int n,m,nn;
ll Power(ll x,ll k)
{
	ll sss=1;
	while (k)
	{
		if (k%2) sss=sss*x%mod;
		x=x*x%mod;
		k/=2;
	}
	return sss;
}
ll ny(ll x){return Power(x,mod-2);}
ll C(int x,int y)
{
	if (y<0 || y>x) return 0;
	if (y==0 && y==x) return 1;
	return jc[x] *jc_ny[x-y]%mod *jc_ny[y]%mod;
}
ll go_to(int x){return C(nn,(nn+x)/2);}
void init()
{
	jc[0]=1; jc_ny[0]=1;
	for (int i=1;i<=nn;++i) jc[i]=jc[i-1]*i%mod;
	jc_ny[nn]=ny(jc[nn]);
	for (int i=nn-1;i>=1;--i) jc_ny[i]=jc_ny[i+1]*(i+1)%mod;
}
int main()
{
	scanf("%d%d",&n,&m);
	if (n<m)
	{
		printf("0\n");
		return 0;
	}
	nn=2*n;
	init();
	ll ans=go_to(0);
	int x=0,y=0,doe=1;
	while (1)
	{
		doe=-doe;
		if (x<y) swap(x,y);
		x=-2-x; y=2*(m+1)-y;
		if (x<-nn && y>nn) break;
		if (x>=-nn) (ans+=go_to(x)*doe)%=mod;
		if (y<=nn) (ans+=go_to(y)*doe)%=mod;
	}
	
	printf("%lld\n",(ans%mod+mod)%mod);
	return 0;
}
--------------------------