ZR1353 20三月省选 Day4 C dict

好题。也是一个会一半的题目,最后一半是一个没怎么见过的套路。

考虑字典序比较,常见的方法是枚举 $\text{LCP}$ 长度,然后固定下一位小于,然后剩下的随便放。

在这个题中,我们一样可以枚举 $\text{LCP}$ 的长度,比如长度为 $k$ ,也就意味着第 $p_1 \dots p_k$ 小在 $A,B$ 中是相等的,而 $A$ 的第 $p_{k+1}$ 小比 $B$ 的小。

我们考虑对两个集合分别排序后处理。对于每个 $k$ ,我们考虑 $p_{k+1}$ 处 $A$ 的取值对答案的影响,设这个位置到左边第一个已经确定的位置中间有 $l$ 个空位,这个位置到右边第一个有 $r$ 个空位,这个位置到两边的值域分别由 $L,R$ 个数,那么贡献是是

而这个位置一旦确定,也就是枚举到了 $k+1$ ,那么相当于是删除前后位置间这一段的贡献,加入新的两段的贡献。明显这个贡献是个组合数。

那么就有了一个不怎么行的算法,用 $\text{set}$ 维护这些段,然后每次暴力枚举这个上面说的贡献,复杂度 $O(nm)$ 。

继续观察,会发现这个操作本质上是在值域上进行一次分裂,把值域 $[L,R]$ 分裂成了 $[L,c-1] , [c+1,R]$ 。我们可以进行启发式分裂,也就是每次枚举小的那一边的话,复杂度就会被降到 $O(n\log m)$ 。可以发现这个式子是一个经典的组合恒等式

所以可以直接减掉一部分得到另一部分。

最后总复杂度变成了 $O(n(\log m + \log n))$ 。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "cassert"
using namespace std;
#define MAXN 500006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
const int P = 998244353;
int n , m;
int A[MAXN] , B[MAXN] , p[MAXN];

int Pow( int x , int a ) {
int ret = 1;
while( a ) {
if( a & 1 ) ret = ret * 1ll * x % P;
x = x * 1ll * x % P , a >>= 1;
}
return ret;
}
int J[MAXN] , iJ[MAXN];
int C( int a , int b ) {
if( a < 0 || b < 0 || a - b < 0 ) return 0;
return J[a] * 1ll * iJ[b] % P * iJ[a - b] % P;
}

struct tcurts {
int l , r , L , R;
tcurts( int l = 0 , int r = 0 , int L = 0 , int R = 0 ) : l(l) , r(r) , L(L) , R(R) {}
bool operator < ( const tcurts& s ) const {
return l == s.l ? r < s.r : l < s.l;
}
};

set<tcurts> S;


void solve() {
J[0] = iJ[0] = 1;
rep( i , 1 , MAXN - 1 ) J[i] = J[i - 1] * 1ll * i % P , iJ[i] = Pow( J[i] , P - 2 ) % P;
cin >> n >> m;
rep( i , 1 , n ) scanf("%d",B + i);
sort( B + 1 , B + 1 + n );
rep( i , 1 , n ) scanf("%d",p + i);
S.insert( tcurts( 1 , n , 1 , m ) );
int as = C( m , n ) , ans = 0;
rep( i , 1 , n ) {
int t = p[i] , c = B[p[i]];
auto s = S.upper_bound( tcurts( t , 0x3f3f3f3f ) ); -- s;
int l = t - s -> l , r = s -> r - t , L = s -> L , R = s -> R;
int tot = C( R - L + 1 , l + r + 1 );
as = as * 1ll * Pow( tot , P - 2 ) % P;
if( c - L <= R - c + 1 ) {
int s = 0;
per( j , c - 1 , L )
s = ( s + C( j - L , l ) * 1ll * C( R - j , r ) ) % P;
ans = ( ans + as * 1ll * s ) % P;
} else {
int s = 0;
rep( j , c , R )
s = ( s + C( j - L , l ) * 1ll * C( R - j , r ) ) % P;
s = ( tot + P - s ) % P;
ans = ( ans + as * 1ll * s ) % P;
}
S.erase( s );
if( l ) S.insert( tcurts( t - l , t - 1 , L , c - 1 ) ) , as = as * 1ll * C( c - L , l ) % P;
if( r ) S.insert( tcurts( t + 1 , t + r , c + 1 , R ) ) , as = as * 1ll * C( R - c , r ) % P;
if( !as ) break;
}
cout << ans << endl;
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/2020/12/28/zr1353-20-san-yue-sheng-xuan-day4-c-dict/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog