【训练记录】6.11 训练笔记

又是营业的时候了.

A

$|T|\leq 10^6$ .

大概就是个简单找性质题。首先不难发现答案上界为 $|T|-1$ 且最初生成的 $k$ 个字符一定会是最终的串的前缀,同时发现这个过程至多会进行 $O(\log_{k}|T| )$ 次。于是就可以直接枚举前缀模拟这个过程,复杂度 $|T|\log |T|$ 。写的时候有点细节啥的。

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
#include <cstdio>

#include <cstring>

#include <algorithm>

typedef long long ll ;

using std :: min ;

const int N = 100010 ;

const ll base = 233 ;
const ll P = 1000000009 ;

int T ;
int n ;
int ans ;

ll L, B ;
ll h[N] ;
ll p[N] ;
char s[N] ;

inline int sub(ll a, ll b){
return ((a - b) % P + P) % P ;
}

inline bool chk(int l1, int r1, int l2, int r2){
if (r2 - l2 != r1 - l1) return 0 ;
int len = r1 - l1 + 1 ; l1 --, l2 -- ;
return (sub(h[r1], p[len] * h[l1]) == sub(h[r2], p[len] * h[l2])) ;
}

int main(){
scanf("%d\n", &T) ; p[0] = 1 ;
for (int i = 1 ; i < N ; ++ i)
p[i] = p[i - 1] * base % P ;
while (T --){
scanf("%s", s + 1) ;
n = strlen(s + 1), ans = 1 ;
for (int i = 1 ; i <= n ; ++ i)
h[i] = h[i - 1] * base % P + s[i] ;
for (int i = 1 ; i <= n ; ++ i)
for ( ; ans < n ; ++ ans){
L = ans, B = L + 1 ;
while (L < n - 1){
long long o = L * B + B ;
int l = 1, r = L, rr ; -- o ;
for (int i = 1 ; i < B ; ++ i){
l = r + 2, r = l + L - 1 ;
rr = min(1ll * n, min(1ll * r, o)) ;
if (!chk(1, L - (r - rr), l, rr))
goto not_ok ; if (r >= o - 1 || r >= n - 1) break ;
}
L = o ;
}
break ;
not_ok : continue ;
}
printf("%d\n", ans + 1) ;
}
}

B

$1\leq n\leq 1000$ 。

有欧拉回路 $\Longleftrightarrow$ 全部的点度数均为偶数。然后就不会了【害怕

正解大概是比较麻烦的构造题。考虑这么一种比较自然的构造思路:尝试构造用的边尽量少的方案。由于题目里没有限制最少,所以这个「尽量少」就只是尽量少。大概是瞎画画可以发现,如果一个奇度点连成了偶度点,那么它可能会影响另外一个奇度点,那么另外的奇度点可能之前变成了偶度点但是现在又变回了奇度点。于是就可以想到建出补图的一棵生成森林来,从叶子开始不断和父亲连边+删点,直到不合法为止。不难知道这样做是对的。

那么在保证都是偶度点之后,问题就变成了如何连边使得这个图连通。发现如果有 $\geqslant 3$ 个连通块,那么就可以每个连通块随便选个点连一个环出来。如果只有 $2$ 个连通块,大概是要比较麻烦地讨论一波,但也不难。

嗯,感觉是个挺需要熟练掌握构造技巧的题目。

C

$0 \leq x+y \leq \sum a_{i} \leq 100,x, y, z \geq 0, n, a_{i} \geq 1$ 。

下文默认把题目里的 $x,y,z$ 替换为 $X,Y,Z$ 。

具体思路大概是分两部分做。首先算出拿到每个花色的概率,然后再算每个花色获胜的概率。

先考虑对于一个固定的花色 $x$ 如何计算其获胜的概率。令 $s=\sum a_i$,小 E 拿了$p_x$ 个,不难知道应该是

然后考虑计算发生的概率。发现如果想要计算一个情况的发生概率,需要确定所有除 $x$ 以外的 $p_y$ 。于是可以用一个背包 $f_{i,v}$ 表示考虑了前 $i$ 个花色、当前花色 $x$ 不计算时,一共选了 $v$ 张卡牌的方案数。转移一波之后就可以知道答案应该为

然后问题就在如何保证 $dp$ 的正确性。考虑如果某种类别的牌拥有的越多,这个颜色的胜率就越大。所以可以先把所有可能出现的概率从小到大排个序——不难知道本质不同的概率是 $O(s)$ 的——那么这样就可以保证所有颜色可以取到的范围单调递增的。是个挺妙的离散化技巧。

然后考虑本质不同的概率,最大不会超过分母,也就是 $\dbinom{100}{50}$ 。所以可以拿 __int128 来存。

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
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std ;

#define fr first
#define sc second

#define il inline

const int N = 1050 ;

typedef long long ll ;

typedef __int128_t bill ;

typedef pair< bill, pair<int, int> > pbii ;

const int P = 998244353 ;

ll ans ;
int mxu[N] ;
int base[N] ;
int f[N][N] ;
int n, m, X, Y, Z ;

vector <pbii> All_pr ;

ll fac[N] = {1} ;
ll inv[N] = {1} ;

template <typename T>
il void add(T &x, ll y, int mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}

il ll expow(ll x, ll y, ll mod = P){
ll res = 1 ;
while (y){
if (y & 1)
res = res * x % mod ;
x = x * x % mod ; y >>= 1 ;
}
return res ;
}
il ll comb(int x, int y){
if (x < y) return 0 ;
return fac[x] * inv[y] % P * inv[x - y] % P ;
}
il ll Pr(int s, int t){
//总共有 s 个,小 a 拿了 t 个.要满足 i+Z<=t i<=t-Z
ll ret = 0 ;
for (int i = 0 ; i <= t - Z && i <= Y ; ++ i)
add(ret, comb(s - t, i) * comb(n - X - (s - t), Y - i) % P) ;
return ret ;
}
il bill bicomb(int x, int y){
bill ret = 1 ;
if (x < y) return 0 ;
for (bill i = x - y + 1 ; i <= x ; ++ i) ret *= i ;
for (bill i = 1 ; i <= y ; ++ i) ret /= i ;
return ret ;
}
il pbii Pr(int col, int s, int t){
bill ret = 0 ;
for (int i = 0 ; i <= t - Z && i <= Y ; ++ i)
ret += bicomb(s - t, i) * bicomb(n - X - (s - t), Y - i) ;
return make_pair(ret, make_pair(col, t)) ;
}
ll solve(int col, int s){
memset(f, 0, sizeof(f)) ; f[0][0] = 1 ;
for (int i = 1 ; i <= m ; ++ i){
if (i == col)
for (int j = 0 ; j <= s ; ++ j) f[i][j] = f[i - 1][j] ;
else {
for (int j = 0 ; j <= s ; ++ j)
for (int k = 0 ; k <= min(j, mxu[i]) ; ++ k)
add(f[i][j], f[i - 1][j - k] * comb(base[i], k) % P) ;
}
}
return f[m][s] ;
}
int main(){
cin >> m >> X >> Y >> Z ;
for (int i = 1 ; i <= m ; ++ i)
cin >> base[i], n += base[i] ;
for (int i = 1 ; i <= n ; ++ i)
fac[i] = fac[i - 1] * i % P ;
inv[n] = expow(fac[n], P - 2, P) ;
for (int i = n - 1 ; i ; -- i)
inv[i] = inv[i + 1] * (i + 1) % P ;
for (int i = 1, k ; i <= m ; ++ i){
k = min(X, base[i]) ;
for (int j = Z ; j <= k ; ++ j)
All_pr.push_back(Pr(i, base[i], j)) ;
}
sort(All_pr.begin(), All_pr.end()) ;
for (int i = 1 ; i <= m ; ++ i)
mxu[i] = min(Z - 1, base[i]) ;
for (auto t : All_pr){
int c = t.sc.fr ;
int o = base[c] ;
int u = t.sc.sc ;
// cout << (ll)t.fr << " " << c << " " << u << '\n' ;
add(ans, comb(o, u) * Pr(o, u) % P * solve(c, X - u) % P) ;
mxu[c] = u ;
}
// printf("%lld\n", ans) ;
printf("%lld\n", ans * expow(comb(n, X) * comb(n - X, Y) % P, P - 2) % P) ; return 0 ;
}