UOJ424【集训队作业2018】 count [* medium]
- 如果一个序列 (a_i) 满足长度为 (n)，(a_iin [1,m])，且 (1sim m) 的所有数均出现过，那么称 (a) 为好序列
- 对于序列 (A)，记 (f_{A}(l,r)) 为 ([l,r]) 内最大值的下标，如果有多个最大值那么取下标最小的。
- 称序列 (A) 和 (B) 同构当且仅当对于所有的 (l,r) 均有 (f_{A}(l,r)=f_B(l,r))
- 求本质不同的好序列的数量。
- (nle 10^5)，答案对 (998244353) 取模。
Solution
先特判掉 (m>n) 的情况。
考虑先确定一个 (f) 数组，然后判定他能否生成一个好序列。
考虑先确定最靠左边的最大值的位置，此时他大于等于后面的元素，然后严格大于前面的元素。
不难发现这种确定方式可以固定一组 (f) 序列，同时，如果这张图上的最长链小于等于 (m)，那么这个答案就是合法的。
观察到我们其实只关心长度，于是我们不难得到 (mathcal O(n^2m)) 的暴力做法。
具体来说，令 (f_{i,j}) 表示长度为 (i) 的序列，最大值为 (j) 的方案数，令 (S_{i,j}) 为其前缀和：
- (f_{i,j}leftarrow dp_{i-1,j-1}) 表示最大值为最后一个元素
- (f_{i,j}leftarrow dp_{i-1,j}) 表示最大值为第一个元素
- (f_{i,j}leftarrow S_{k-1,j-1}dp_{i-k-1,j}+dp_{k-1,j-1}S_{i-k-1,j-1})
具体来说，我们发现这个实际上是一个树计数的过程，我们考虑一棵二叉树，左儿子的边为蓝色，右儿子的边为红色，一棵树合法当且仅当其不存在一个点走到根节点需要经过 (m) 条蓝边。
这样的话我们考虑直接对 (S) 序列进行计数，方便起见我们认为初始的答案为 (1)，同时规定 (S_{0,0}=1)，不难发现：
- (S_{i,j}leftarrow S_{k-1,j-1}S_{i-k,j})
边界为 (S_{0,?}=S_{1,x(xge 1)}=1)，答案为 (S_{n,m})
这个式子看上去就非常的卷积，我们从小到大枚举 (j)，记 (f_j(x)) 表示其生成函数 (sum S_{i,j}x^i)
不难发现：(f_j(x)=f_j(x)f_{j-1}(x)x+1) 于是得到 (f_j(x)=frac{1}{1-f_{j-1}(x)x})
考虑一类函数复合，(G(f(x))=frac{1}{1-f(x)x})，我们希望求得是 (G(G(...G(frac{1}{1-x}))))
基于观察，我们发现答案一定可以写成 (frac{A(x)}{B(x)})
这样的话递推形式即为 (frac{1}{1-frac{A(x)}{B(x)}x}=frac{B(x)}{B(x)-A(x)x})
可以写成矩阵的形式，通过矩阵快速幂 +NTT 处理即可，复杂度 (mathcal O(nlog^2 n))
最后还要多项式求逆一下。
有没有更 easy 的做法呢？当然是有的！
注意到，这个题只需要我们算出其中一项 (f_m[x^n])，所以我们可以考虑一下奇怪的trick：
我们希望计算二叉树的数量，可以考虑计算括号序列的数量，根据此题模型，我们可以考虑一个这样的转换：
- 对这棵树做 Dfs，然后在左子树形成的括号序列上加上一对括号在边界，然后剩余的即为右子树。
然后基于这样的观察我们发现任意的一个括号序列都是合法的，将左括号设为 (+1)，右括号设为 (-1) 问题等价于配对的括号序列使得不存在前缀和大于 (m)（此时假设前缀和为 (x) 等价于往 (l) 子树走了 (x-1) 步）这样的话我们给 (m+1)，然后就是大于等于 (m) 了。
套路，不妨从坐标系的角度考虑（ (y) 表示左括号，(x) 表示右括号）我们等价于计算有多少条路径，满足不经过 (y=x-1) 和 (y=x+m)，求走到 ((n,n)) 的方案数。
这样的话，仿照 [JLOI2015]骗我呢 进行处理即可，复杂度 (mathcal O(n))
答案等于总方案数减去至少经过了 A，至少经过了 B，加上至少经过了 AB，至少经过了 BA，减去 ... 依次类推。
预处理组合数即可。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int P = 998244353 ;
const int N = 2e5 + 5 ;
int n, m, Ans, maxn, fac[N], inv[N] ;
struct node {
int x, y ;
node(int _x = 0, int _y = 0) { x = _x, y = _y ; }
} Ed ;
int fpow(int x, int k) {
int ans = 1, base = x ;
while(k) {
if(k & 1) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
int C(int x, int y) {
if(x < 0 || y < 0 || x < y) return 0 ;
return fac[x] * inv[y] % P * inv[x - y] % P ;
}
int operator - (node a, node b) {
int dx = a.x - b.x, dy = a.y - b.y ;
return C(dx + dy, dx) ;
}
node F(node x, int b) {return node(x.y - b, x.x + b) ;}
int Get(node x, int type) {
if( (Ed - x) == 0 ) return 0 ;
return ( (Ed - x) - Get(F(x, (type) ? -1 : m), type ^ 1) + P ) % P;
}
signed main()
{
n = gi(), m = gi(), maxn = n * 2 ;
if( m > n ) { puts("0") ; exit(0) ; }
fac[0] = inv[0] = 1, ++ m ;
rep( i, 1, maxn )
fac[i] = fac[i - 1] * i % P, inv[i] = fpow(fac[i], P - 2) ;
Ans = C(n + n, n) ; Ed = node(n, n) ;
Ans = Ans - Get(F(node(0, 0), -1), 0) ;
Ans = Ans - Get(F(node(0, 0), m), 1) ;
Ans %= P, Ans = (Ans + P) % P ;
cout << Ans << endl ;
return 0 ;
}