Asusetic
0%

2021.04.19模拟赛

发表于 分类于 Valine：
本文字数： 987 阅读时长 ≈ 1 分钟

很久之前的东西

2021.04.19 模拟赛

T1 青蛙

题面

求第 kk 大这个操作可以类似滑动窗口一个个扫过去

求完之后就是置换的 mm 次幂，mm 不太大所以完全可以倍增水过去（需要滚动数组一下） O(nlog⁡n)O(n\log n)

如果很大可以考虑找环，找到之后减去柄长模环，复杂度 O(n)O(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
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1000005;
int n, k;
ll m;
ll a[N];
int ans[N];
int pos[N][2];
int main() {
    scanf("%d%d%lld", &n, &k, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        ans[i] = i;
    }
    ll l = 1, r = k + 1;
    for (int i = 1; i <= n; i++) {
        while (r < n && a[r + 1] - a[i] < a[i] - a[l]) {
            l++;
            r++;
        }
        pos[i][0] = (a[r] - a[i] > a[i] - a[l] ? r : l);
    }
    int now = 1;
    for (ll i = 0; (1ll << i) <= m; i++) {
        int now = (i & 1);
        if (m & (1ll << i)) {
            for (int j = 1; j <= n; j++) {
                ans[j] = pos[ans[j]][now];
            }
        }
        for (int j = 1; j <= n; j++) {
            pos[j][now ^ 1] = pos[pos[j][now]][now];
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}
// Asusetic eru quionours

T2 环

题面

看起来就很差分约束，如果固定了长度判断有解就按照限制连边，正整数的限制意味着 i→i+1i \rightarrow i+1 至少是 11 ，还需要按是否跨过零点分类讨论一下

二分一个答案区间不太现实，考虑二分上下界，那我们需要知道某个条件下需要向大还是向小调整

如果无解肯定是负环，我们希望知道负环上每个边的与总长度的关系

即当总长度变大/小时它怎么变，变大变小分别记作 1,−11,-1，无关为 00，如果这些和是正的说明需要调大总长度才能无负环，反之同理

这样就能二分出上下界

复杂度 O(n2log⁡w)O(n^2\log w)

还没码

T3 小基的高智商测试

题面

阅读理解题

先把相等的点用并查集放一起，然后按小于连边

先排除掉环一类的无解情况，剩下的就是一个森林

连上一个虚点就能得到一个树，一开始以为是拓扑序计数，发现这个同一层的点是可以相等的

考虑直接钦定排名，相等的拿到同一个排名

令 fif_i 表示用 1∼i1\sim i 的数字分配排名的方案数，那么树上DP

设 dpx,idp_{x,i} 为 xx 的子树用 1∼i1 \sim i 的分配方案，于是 dpx,i=dpx,i−1+∏v∈son(x)dpv,j−1dp_{x,i}=dp_{x,i-1}+\prod\limits_{v\in son(x)}dp_{v,j-1}

即分配 1∼j−11\sim j-1 的方案和钦定自己分配 jj 的方案

但是发现这么定义的问题是可能有的排名没分配出去，二项式反演一下解决

即 fi=∑(ij)gj⇒gi=∑(−1)j(ij)fi−jf_i=\sum\binom{i}{j}g_j \Rightarrow g_i=\sum(-1)^j\binom{i}{j}f_{i-j}

复杂度 O(n2)O(n^2)

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <map>
using namespace std;
const int N = 5005;
typedef long long ll;
const ll mod = 1e9 + 7;
int n, m;
enum Type {
    VOID = -1,
    Equal,
    Less,
};
struct Oper {
    int u, v;
    Type typ;
} q[N];
struct Edge {
    int v;
    int nxt;
} edge[N * 2];
int head[N], ecnt;
void add(int u, int v) {
    edge[++ecnt].v = v;
    edge[ecnt].nxt = head[u];
    head[u]        = ecnt;
}
int fa[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    x     = find(x);
    y     = find(y);
    fa[x] = y;
}
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
ll fac[N], ifac[N];
void init() {
    fac[0] = 1;
    for (int i = 1; i <= n + 1; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n + 1] = qpow(fac[n + 1], mod - 2);
    for (int i = n; i >= 0; --i) {
        ifac[i] = 1ll * ifac[i + 1] * (1ll * i + 1ll) % mod;
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int in[N];
int dp[N][N];
bool G[N][N];
bool vis[N], flag = 1;
void dfs(int x) {
    if (vis[x]) {
        cout << 0 << endl;
        exit(0);
    }
    vis[x]  = 1;
    int cnt = 0;
    for (int i = head[x]; i; i = edge[i].nxt) {
        int v = edge[i].v;
        dfs(v);
        cnt++;
    }
    if (cnt) {
        for (int i = 1; i <= n; i++) {
            dp[x][i] = 1;
        }
        for (int i = head[x]; i; i = edge[i].nxt) {
            int v = edge[i].v;
            for (int j = 1; j <= n; j++) {
                dp[x][j] = 1ll * dp[x][j] * dp[v][j - 1] % mod;
            }
        }
        for (int i = 1; i <= n; i++) {
            dp[x][i] = (1ll * dp[x][i] + 1ll * dp[x][i - 1] % mod) % mod;
        }
        return;
    } else {
        for (int i = 1; i <= n; i++) {
            dp[x][i] = i;
        }
    }
}
ll C(int n, int m) {
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int main() {
    cin >> n >> m;
    char rub[3];
    init();
    for (int i = 1; i <= m; i++) {
        cin >> q[i].u >> rub >> q[i].v;
        if (rub[0] == '=') {
            q[i].typ = Equal;
            merge(q[i].u, q[i].v);
        } else {
            q[i].typ = Less;
        }
    }
    for (int i = 1; i <= m; i++) {
        if (q[i].typ == Equal) {
            continue;
        }
        int x = find(q[i].u), y = find(q[i].v);
        if (!G[x][y]) {
            add(x, y);
            G[x][y] = 1;
        }
        in[y]++;
    }
    bool QAQ = 1;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i && in[i] == 0) {
            add(0, i);
            QAQ = 0;
        }
    }
    n++;
    dfs(0);
    for (int i = 1; i <= n - 1; i++) {
        if (!vis[find(i)]) {
            cout << 0 << endl;
            return 0;
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j & 1) {
                ans = (ans + mod - (1ll * C(i, j) % mod * dp[0][i - j]) % mod) %
                      mod;
            } else {
                ans = (ans + 1ll * C(i, j) % mod * dp[0][i - j] % mod) % mod;
            }
        }
    }
    cout << ans << endl;
}
// Asusetic eru quionours