首页 模拟赛

最大流，数数 + 二项式反演，分块 + manacher

# A. 【余姚精选20套day2T1】收藏家

先把问题做个转化：每个人手上有一个物品，并且第 ii 个人一次至多持有aia_i 个物品，每次操作一个人可以把一个物品给另一个人，问最后第 1 个人至多有多少个物品。

考虑构建最大流模型。

建超级源点 ss 向每个人连流量为 1 的边，然后从 1 向超级汇点 tt 连流量为 a1a_1 的边。

对于每次交换的两个人 x,yx, y，可以选择给或者不给：

  • 给：在 idxid_x 和 idyid_y 之间连一条流量为 1 的双向边。
  • 不给：对 x,yx, y 分别新建一个点，然后从 idxid_x 向 new_idxnew\_id_x 连一条流量为 axa_x 的边，yy 同理。

然后跑一遍 dinic\text{dinic} 即可。

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
#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 3e5;
const int INF = 1e9;
int T, n, m, ans, s, t, cnt;
int a[N], x[N], y[N], id[N];
struct node{
    int v, w, nxt;
}edge[N << 4];
int head[N], tot = 1;

inline void add(int x, int y, int z){
    edge[++tot] = (node){y, z, head[x]};
    head[x] = tot;
}

inline void Add(int x, int y, int z){
    add(x, y, z), add(y, x, 0);
}

int dep[N];

inline bool bfs(){
    queue <int> q;
    memset(dep, 0, sizeof(dep));
    q.push(s), dep[s] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = head[x], y; i; i = edge[i].nxt)
            if(edge[i].w && !dep[y = edge[i].v]) dep[y] = dep[x] + 1, q.push(y);
    }
    return dep[t];
}

inline int dfs(int x, int lim){
    if(x == t || !lim) return lim;
    int flow = 0;
    for(int i = head[x]; i; i = edge[i].nxt){
        int y = edge[i].v;
        if(edge[i].w && dep[y] == dep[x] + 1){
            int res = dfs(y, min(lim, edge[i].w));
            lim -= res, flow += res, edge[i].w -= res, edge[i ^ 1].w += res;
        }
    }
    if(!flow) dep[x] = 0;
    return flow;
}

inline void dinic(){
    while(bfs()) ans += dfs(s, INF);
}

signed main(){
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    T = read();
    while(T--){
        n = read(), m = read();
        memset(head, 0, sizeof(head));
        s = tot = 1, t = cnt = 2, ans = 0;
        for(int i = 1; i <= n; ++i){
            a[i] = read(), id[i] = ++cnt;
            Add(s, id[i], 1);
        }
        for(int i = 1; i <= m; ++i){
            int x = read(), y = read();
            if(x == y) continue;
            add(id[x], id[y], 1), add(id[y], id[x], 1);
            Add(id[x], ++cnt, a[x]), id[x] = cnt;
            Add(id[y], ++cnt, a[y]), id[y] = cnt;
        }
        Add(id[1], t, a[1]), dinic();
        write(ans), puts("");
    }
    return 0;
}
// X.K.

# B. 【余姚精选20套day17T1】三视图

毒瘤数数题。

考虑对于行，列从大到小排序之后依次处理，不难发现这样是不影响答案的。

然后大的数看管的行列我们就不需要再考虑了。

（借用一下 RenamoeRenamoe 学长的图qwq）

假设 c×dc \times d 的矩形已经合法，我们要填剩下的三个矩形，满足 (a+c)×b(a + c) \times b 和 a×(b+d)a \times (b + d) 的矩形最大值都为 kk。

考虑二项式反演。

设 fif_i 表示 aa 行中钦定 ii 行不合法，gig_i 为恰好 ii 行不合法，那么：

fi=∑j=ia(ij)gjf_i = \sum_{j = i}^a\dbinom{i}{j}g_j

fif_i 为：

fi=(ai)(ki((k+1)a+c−i−ka+c−i))b(ki(k+1)a−i)df_i = \dbinom{a}{i}(k^i((k + 1)^{a + c - i} - k^{a + c - i}))^b(k^i(k + 1)^{a - i})^d

答案 g0g_0 就是：

g0=∑i=0a(−1)i(i0)fig_0 = \sum_{i = 0}^a(-1)^i\binom{i}{0}f_i

对于所有的 kk 乘起来即可。

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
#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5;
const int mod = 1e9 + 9;
int n, m, cnt, l1, r1, l2, r2, ans = 1;
int a[N], b[N], p[N], fac[N], ifac[N];

inline int qpow(int a, int b){
    int res = 1;
    while(b){
        if(b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod, b >>= 1;
    }
    return res;
}

inline void init(int n){
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = qpow(fac[n], mod - 2);
    for(int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
}

inline int C(int n, int m){
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

inline int f(int l1, int l2, int r1, int r2, int k, int i){
    int len1 = l2 - l1 + 1, len2 = r2 - r1 + 1, res = 1;
    res = 1ll * res * C(len1, i) % mod * qpow(k, i * r2) % mod;
    res = 1ll * res * qpow((qpow(k + 1, l2 - i) - qpow(k, l2 - i) + mod) % mod, len2) % mod;
    res = 1ll * res * qpow(k + 1, (len1 - i) * (r1 - 1)) % mod;
    return res;
}

inline int solve(int l1, int l2, int r1, int r2, int k){
    int len = l2 - l1 + 1, res = 0;
    for(int i = 0; i <= len; ++i)
        res = (res + (i & 1 ? -1ll : 1ll) * f(l1, l2, r1, r2, k, i) + mod) % mod;
    return res;
}

signed main(){
    init(N - 1);
    n = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), p[++cnt] = a[i];
    m = read();
    for(int i = 1; i <= m; ++i) b[i] = read(), p[++cnt] = b[i];
    sort(a + 1, a + 1 + n), reverse(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + m), reverse(b + 1, b + 1 + m);
    if(a[1] != b[1]) return puts("0"), 0;
    sort(p + 1, p + 1 + cnt);
    int tot = unique(p + 1, p + 1 + cnt) - p - 1;
    reverse(p + 1, p + 1 + tot);
    for(int i = 1; i <= tot; ++i, l1 = l2, r1 = r2){
        l2 = l1, r2 = r1;
        while(l2 + 1 <= n && a[l2 + 1] == p[i]) l2++;
        while(r2 + 1 <= m && b[r2 + 1] == p[i]) r2++;
        ans = 1ll * ans * solve(l1 + 1, l2, r1 + 1, r2, p[i]) % mod;
    }
    write(ans), puts("");
    return 0;
}
// X.K.

# C. 【余姚精选20套day14T2】回文子串

暴力 manacher\text{manacher} 可得 70pts，然而跟 kk 去 min⁡\min 的地方有一点小边界，考场上每大样例，然后也没注意到，遗憾只得了 30pts qwq

分块维护哈希或马拉车，或者线段树维护。

然而还没有改，先咕了。

更新于 阅读次数 次