「UOJ424」集训队作业2018 count

杂题 / uoj
Word count: 2k   |   Reading time≈ 8 min

反复翻折法

Solution

题目中的限制实在太奇怪了，直接做肯定不怎么能做，我们考虑转化一下。

我们仔细阅读题中同构的限制，发现两个序列同构等同于两个序列建出来的笛卡尔树同构。于是这个奇怪的题意就被我们转化成满足值域为 $[1,m]$ 的序列的本质不同的笛卡尔树计数。

然后考虑序列中的每一个数在 $[1,m]$ 之间并且 $[1,m]$ 的每个数都出现过在笛卡尔树上的限制是什么。这里给出结论，对于笛卡尔树上任意一个点到根的路径上，都满足这条路径上向左走的边的数量小于 $m$ 。

首先证明这个限制的必要性，如果对于一棵笛卡尔树，存在一个点到根的路径左边个数大于 m，那么从根出发，每次我们向左走一步，这个数都必须 -1，就算根的值填 m，这个点的值都会小于 0，一定是不可行的。

然后证明充分性，对于一棵符合条件的树，我们可以构造出一个方案满足条件。首先我们找出树上最长的左链，把链上的每个点的值设成 $m - 这个点到根的路径上左边的数量$ ，如果在 $[1,m]$ 中还有未出现的数，那么找出树中剩下的点中深度（也就是到根的路径上左边数量）最深的点设成未出现中的数中最小的数。最后把每个数设成他的父亲的值减去他到父亲的边是否是左边。

好了 ，现在这个题就变成了统计有多少个 n 个点笛卡尔树，满足最大左链深度小于 m。

我们发现还是不怎么好做，于是我们再做一个转化，众所周知，一个多叉树可以通过一个法则转成二叉树，法则为 “左边儿子，右边兄弟”，具体转法可以参见这个博客：

多叉树转二叉树

通过这个转换法则，我们发现 n 个点的多叉树会转化为一个 n 个点的二叉树，但是这个二叉树的根节点只有一个左儿子，如果我们把这个二叉树的根节点删掉，那么 n 个点的多叉树就可以和 n-1 个点的二叉树一一对应。同时，经过这个转化过后，二叉树上的某个点到根的路径权值就等同于这个点转化后在多叉树上的深度 -1。

于是，原本我们要计算上面那个奇怪限制笛卡尔树的数量，变成了一个有最大深度限制的一般树数量计数。

但是这个东西直接做还是不怎么好做，我们把数的计数转化为这个树的括号序计数。如果把一个 ‘(‘ 看做 +1，把 ‘)’ 看做 -1，一个点在树上的深度就是这个点的括号序前缀和。如果我们把根节点的那个大括号去掉，那么这个数的括号序和合法的括号序一一对应了。

于是最后的最后，这个题的题意变成了，求长度为 2n 的合法括号序，满足这个括号序的前缀和不超过 m。

我们把括号序看做在坐标系上从 (0,0) 开始走，一个左括号看做(1, 1)，一个右括号看做(1, -1) 。一个合法的括号序就是一个从 (0, 0) 到 (2n, 0) 的路径，但是不能碰到直线 $y = -1$。只有这一个限制的话有一个经典做法就是对称法。但是这个题中还有一个前缀和的限制，在图上就是不能碰到 $y = m +1$ 这条直线。

有两个限制就不能直接对称法做了，我们要用一个跟厉害的科技 - 多次对称法。我们把违反了 $y=-1$ 的限制称作事件 a，把违反了 $y = m +1$ 的限制称作事件b，考虑用容斥计算合法方案数。我们枚举一个违法序列形如 ababab… 然后计算有多少种违法序列含有这个子序列，贡献是 $(-1)^{len}$ ，计算这样的序列个数就是我们先把起点沿 $y=-1$ 对称，再沿另一条直线对称，一直多次对称，然后算方案数即可，注意到每次对称起点 y 坐标的绝对值都会变大，而当起点的 y 坐标觉得值大于 $2n$ 后方案数一定为 0，所以这个过程至多重复 $O(n)$ 次。当然形如 ababa… 的违法序列也要算一遍。经过观察发现，对于任意一个不合法的序列 aaa…aabb…bbaaaa..aabbb..bb ，都会被减去恰好一次，于是我们就算出了这样符合条件的路径的数量。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 2e6 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
const ll mod = 998244353 ;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> iv red(T &x) { x -= mod, x += x >> 31 & mod;}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

ll n, m, ans;

ll fac[maxn], inv[maxn];

ll power(ll a, ll b)
{
    ll ret = 1;
    for(; b; b >>= 1, (a *= a) %= mod) if(b & 1) (ret *= a) %= mod;
    return ret;
}

void init()
{
    ll n = 2e6;
    fac[0] = 1;
    rep(i, 1, n) fac[i] = fac[i - 1] * i % mod;
    inv[n] = power(fac[n], mod - 2);
    per(i, n, 1) inv[i - 1] = inv[i] * i % mod;
}

ll binom(ll n, ll m)
{
    return n < m ? 0 : fac[n] * inv[m] % mod * inv[n - m] % mod;
}

ll calc(ll x)
{
    if((2 * n - x) % 2 == 1) return 0;
    ll a = (2 * n - x) / 2;
    return binom(2 * n, a);
}

signed main()
{
    init();
    n = read(), m = read();
    if(n < m) return puts("0"), 0;
    ans = calc(0);
    ll x = -2, coef = mod - 1;
    while(abs(x) <= 2 * n)
    {
        red(ans += coef * calc(abs(x)) % mod);
        coef = mod - coef;
        coef == 1 ? x = 2 * (m + 1) - x : x = -2 - x;
    }
    x = 2 * (m + 1), coef = mod - 1;
    while(abs(x) <= 2 * n)
    {
        red(ans += coef * calc(abs(x)) % mod);
        coef = mod - coef;
        coef == 1 ? x = -2 - x : x = 2 * (m + 1) - x;
    }
    printf("%lld\n", ans);
    return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信