Educational Codeforces Round 142 (Rated for Div. 2)

A. GamingForces

每次打两个的技能只对两个 \(1\) 有效。

1
2
3
int n = rd(), cnt = 0;
for (int i = 1; i <= n; ++i) cnt += (rd() == 1);
printf("%d\n", n - cnt + cnt / 2 + cnt % 2);

B. Stand-up Comedian

先 a 再轮流 bc 最后 d 。

1
2
3
int a = rd(), b = rd(), c = rd(), d = rd();
if (b < c) swap(b, c);
printf("%d\n", a ? a + c * 2 + min(a + 1, b - c + d) : 1);

C. Min Max Sort

一个排列，每次可以选两个数 \(x,y\) ，将两者较小的移到开头，较大的移到结尾。

问排成增序所需最小操作次数。

倒着考虑，如果最后结束的时候开头不是 \(1\) ，结尾不是 \(n\) ，就一定要选一次 \((1, n)\) 。

以此类推，每次把最小和最大两个数删除，直到剩余序列是排序好的为止。懒删除复杂度 \(O(n)\) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define N 200007 
int a[N];
bool vis[N];
inline void work() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {vis[i] = false; a[i] = rd();}
    int ans = 0;
    for (int i = 1, l = 1, r = n; l < r; ++i) {
        while (vis[a[l]]) ++l;
        while (vis[a[r]]) --r;
        if (l >= r) break;
        if (a[l] != i || a[r] != n - i + 1) ans = i;
        vis[i] = vis[n - i + 1] = true; 
    }
    printf("%d\n", ans);
}

D. Fixed Prefix Permutations

反演一下，考虑 \(a_j\) 能对每个 \(a_i\) 产生多少贡献，容易发现是 \(a_j\) 的逆和 \(a_i\) 的最长公共前缀。

把所有 \(a_j\) 的逆建一棵 Trie ，然后答案就是 \(a_i\) 在 Trie 上能跑到的最深的深度。复杂度 \(O(nm)\) 。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr     first
#define sc     second
#define mp     make_pair
#define mt     make_tuple
#define pb     push_back
#define eb     emplace_back
#define all(x) (x).begin(), (x).end()

inline T rd() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int n, m, tot;

struct node {
    int son[10];
    void clear() {for (int i = 0; i < 10; ++i) son[i] = 0;}
} c[1000007];

inline void insert(vector<int> &s) { // build trie
    int rt = 0;
    for (int j = 0; j < m; ++j) {
        if (!c[rt].son[s[j]]) c[rt].son[s[j]] = ++tot;
        rt = c[rt].son[s[j]];
    }
}

inline int search(vector<int> &s) { // find the max depth s could reach
    int rt = 0;
    for (int j = 0; j < m; ++j) {
        if (!c[rt].son[s[j]]) return j;
        rt = c[rt].son[s[j]];
    }
    return m;
}

vector<int> a[50007], rev;

inline void work() {
    n = rd(); m = rd(); rev.resize(m);
    for (int i = 0; i < n; ++i) {
        a[i].clear();
        for (int j = 0; j < m; ++j) {
            int x = rd() - 1;
            rev[x] = j; a[i].push_back(x);
        }
        insert(rev);
    }
    for (int i = 0; i < n; ++i) printf("%d ", search(a[i])); 
    puts("");
    for (int i = 0; i <= tot; ++i) c[i].clear(); 
    tot = 0;
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

E. Divisors and Table

给定 \(m_1, m_2\ (m_1,m_2\le 10^9)\) ，问 \(m_1\times m_2\) 有多少个因子出现在了 \(n\times n\) 的乘法表里。

此外，对于所有出现因子，求出来该因子出现的最小的行数。输出这些行数的异或和。

\(m_1m_2\le 10^{18}\) ，至多 \(10^6\) 个因子，\(15\) 个质因子，分开给的目的应该是不用 pollard rho。

那么对于每个因子 \(x\) ，保证列合法，找到其不超过 \(n\) 的最大的因子 \(y\) ，那么最小的行就是 \(x/y\) 。

假设这样的 \(y\) 叫 \(mx[x]\) ，使用搜索的方法生成因子 \(x\) ，那么 \(mx[x]\) 这个数组是可以递推的。

（对于某个 \(x\) 和 \(x\) 包含的质因子 \(p_i\) ， \(mx[x]\) 可能的来源只有 \(mx[x/p_i]\) 或 \(mx[x/p_i] * p_i\) ）

搜索的计算量是 \(\sum_{x|m_1m_2}\) \(x\) 的质因子个数，因此不会超过 \(15\times 10^6\) 可以接受。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define T int 
typedef pair<T, T> pii;
typedef tuple<T, T, T> tii;

#define fr     first
#define sc     second
#define mp     make_pair
#define mt     make_tuple
#define pb     push_back
#define eb     emplace_back
#define all(x) (x).begin(), (x).end()

inline T rd() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

#define N 5007

vector<int> d, fac; // fac : prime factors of nw

vector<pii> s; // prime factors of m1m2

unordered_map<ll, ll> mx; // maximum divisor <= n

int n, tot, ans;

void dfs(ll nw, int step) {
    if (step == s.size()) return;
    dfs(nw, step + 1);
    auto [p, t] = s[step];
    fac.push_back(p);
    for (; t; --t) {
        nw *= p;
        for (auto x : fac) {
            ll y = mx[nw / x];
            mx[nw] = max(mx[nw], (y * x <= n ? y * x : y));
        }
        if (nw / mx[nw] <= n) {++tot; ans ^= nw / mx[nw];}
        else break;
        dfs(nw, step + 1);
    }
    fac.pop_back();
}

inline void work() {
    n = rd(); 
    mx.clear(); d.clear(); s.clear(); 
    mx[1] = 1; tot = ans = 1; 

    auto getd = [&](int x) {
        int lim = sqrt(x);
        for (int i = 2; i <= lim && i <= x; ++i) 
            while (x % i == 0) {d.pb(i); x /= i;}
        if (x > 1) d.pb(x);
    };
    getd(rd()); getd(rd()); sort(all(d));

    int lst = 0, cnt = 0;
    for (auto x : d)
        if (x != lst) {
            if (lst) s.eb(lst, cnt);
            lst = x; cnt = 1;
        } else ++cnt;
    s.eb(lst, cnt);

    dfs(1, 0);
    printf("%d %d\n", tot, ans);
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}

F. Graph Coloring

给 \(n\) 个点的完全图的边红蓝染色，求染色方案数模 \(998244353\) ，满足：

  • 至少有一条红边，至少有一条蓝边
  • 对于任何一个大于 \(2\) 的点集，其导出子图是红连通或蓝连通的，但不同时成立。

结论：若一幅图不连通，则其补图连通。

归纳证明，首先 \(1\) 个点的时候成立。假设 \(k\) 个点成立，那么对于新增的一个点：

  • 与 \(k\) 个点都连通，那么图中该点连通了所有点。
  • 与 \(k\) 个点都不连通，那么补图中该点连通了所有点。
  • 与一些点有边一些点无边，则原图连通即可连上该点，原图不连通则补图即可连上该点。

所以计数时只需要保证红蓝不同时连通即可。

假设 \(n\) 个点的答案为 \(A_n\) ，对于任意一个解边颜色取反仍然是一个解。

因此我们计数 \(n\) 个点，全集只被蓝色连通的方案数 \(B_n\) ，有 \(A_n=2\times B_n\) （特殊 \(A_1=B_1=1\) ）。

递推考虑 \(1\) 号点被加入的情况。

对于 \(1\) 号点所在的红色连通分量（极大），由定义每个点和分量外的点的边都是蓝色。

这时想要把 \(1\) 号点蓝连通加入，则必定要选分量内的点和分量外的点的边。

无论分量外的点之间的边如何染色，这幅图的生成树必定包含蓝色的边，由开始的结论这幅图只能是蓝连通。

因此递推枚举红色连通分量的大小 \(k\) ，则分量内方案数 \(B_k\) ，分量外方案数 \(A_{n-k}\) ，有： \[ B_n =\sum_{k=1}^{n-1} {n - 1\choose k - 1} B_k A_{n-k},\ n>1 \] 递推复杂度 \(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

#define N 5007
#define mod 998244353

int fac[N], ifac[N];
 
inline int fpow(int x, int t = mod - 2) {
    int res = 1;
    for (; t; t >>= 1, x = 1ll * x * x % mod)
        if (t & 1) res = 1ll * res * x % mod;
    return res;
}
 
inline ll C(int n, int m) {
    if (n < m) return 0;
    return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

int b[N] = {0, 1}, a[N] = {0, 1};

int main() {
    int n = rd();
    fac[0] = ifac[0] = 1;
    rep(i, 1, n) fac[i] = 1ll * fac[i - 1] * i % mod;
    ifac[n] = fpow(fac[n]);
    per(i, n - 1, 1) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;
    rep(i, 2, n) {
        rep(j, 1, i - 1) b[i] = (b[i] + C(i - 1, j - 1) * b[j] % mod * a[i - j]) % mod;
        a[i] = 2 * b[i] % mod;
    }
    printf("%d\n", (a[n] + mod - 2) % mod); // 去掉全红/蓝的情况
    return 0;
}

整理系数之后就可以分治 NTT 计算了。复杂度 \(O(n\log ^2 n)\) 。