RenaMoe's Blog

念念不忘，必有回响

0%

20年12月1日 模拟赛

发表于 更新于 分类于 Valine：

博弈论 + 模拟 + 贪心 + 状压 DP。

100(?) + 40(?) + 60 + 10 = 210（数据太水了）

48 + 20 + 60 + 10 = 138。

T1 树树

给出 \(n\) 个点的树，两人轮流染色，先手染黑，后手染白，染完后若存在一个黑点相邻的都是黑点则先手赢。问结局。

\(2\le n \le 10^5\)。

原题 AGC014D Black and White Tree

博弈论 + DP。

一些显然的性质（考场上写的部分分）：

  • 一条链，奇数个点先手赢；
  • 树上某一个点有大于等于两个叶子节点，先手赢。

正解

若一个点出度为二，且有一个儿子为叶子，先手一定会选择她，后手会选择那个叶子。

这两个点染完色对上方的点没有影响，相当于从原树中删去，剩下的树再如此考虑。

直到只剩根节点，或者某一个点有大于等于两个叶子节点，判先手赢。

可以发现这个 DP 过程就是树上完美匹配。

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
const int N = 1e5 + 9;

struct Graph {
    int cnt;
    int head[N], nxt[N * 2], to[N * 2];
    inline void add(int u, int v) {
        ++cnt, nxt[cnt] = head[u], to[cnt] = v, head[u] = cnt;
        ++cnt, nxt[cnt] = head[v], to[cnt] = u, head[v] = cnt;
    }
} G;

int n;
int size[N];

void dfs(int u, int fa) {
    for (int i = G.head[u]; i; i = G.nxt[i]) {
        int v = G.to[i];
        if (v == fa) continue;
        dfs(v, u);
        if (size[v] == 2) continue;
        size[u] += size[v];
    }
    if (size[u] >= 2) {
        puts("First");
        exit(0);
    }
    ++size[u];
}

inline void main() {
    read(n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        read(u), read(v);
        G.add(u, v);
    }
    dfs(1, 0);
    if (size[1] & 1) puts("First");
    else puts("Second");
}

T2 网格

T3 有手就行

给出 \(n\) 个物品，每个物品有两个权值 \(a_i,b_i\)，一个物品最多选 \(3\) 次：第一次 \(a_i\)，第二次 \(b_i\)，第三次 \(a_i\)。

\(f(i)\) 为选 \(i\) 个物品最大权值和，求 \(\displaystyle \operatorname{xor}_{i=1}^mf(i)\)。

\(1\le n\le 5\times 10^6,1\le m\le 3\times n\)。

一个物品选 \(1\dots3\) 次的状态可以拆成两个物品：\(A_i=a_i\) 和 \(B_i=a_i+b_i\)，两类物品空间为 \(1\) 和 \(2\)。

发现物品空间只有两种，可以贪心地将两类物品从大到小排序，之后 DP 就轻松了。

设 \(f_i\) 为选 \(i\) 个物品最大权值和，每个状态同时维护两类物品分别取到了第几个 \(p^A_i,p^B_i\)： \[ \large f_i\leftarrow \max\{f_{i-1}+A_{p^A_{i-1}},\quad f_{i-2}+B_{p^B_{i-2}}\} \] 复杂度就是 \(\mathcal O(n\log n + 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
typedef unsigned long long ull;
typedef long long LL;

const int threshold = 10000000;
const int N = 2e7 + 9;

ull k1, k2;
inline ull Rand() {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

int n, m;
LL ans;
LL a[N], b[N], f[N];
int pa[N], pb[N];

inline void gen(int n, ull _k1, ull _k2) {
    k1 = _k1, k2 = _k2;
    for (int i = 1; i <= n; ++i) {
        a[i] = Rand() % threshold + 1;
        b[i] = Rand() % threshold + 1;
    }
}

int main() {
    ull k1, k2;
    cin >> n >> m >> k1 >> k2;
    gen(n, k1, k2);
    for (int i = 1; i <= n; ++i) b[i] += a[i];
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    
    pa[0] = pb[0] = 1;
    f[1] = a[1];
    pa[1] = 2, pb[1] = 1;
    for (int i = 2; i <= m; ++i) {
        if (pa[i - 1] <= n && (f[i - 1] + a[pa[i - 1]] > f[i - 2] + b[pb[i - 2]])) {
            f[i] = f[i - 1] + a[pa[i - 1]];
            pa[i] = pa[i - 1] + 1;
            pb[i] = pb[i - 1];
        }
        else {
            f[i] = f[i - 2] + b[pb[i - 2]];
            pa[i] = pa[i - 2];
            pb[i] = pb[i - 2] + 1;
        }
    }
    for (int i = 1; i <= m; ++i) ans ^= f[i];
    cout << ans << endl;
    
    return 0;
}

T4 求余数

有多少长度为 \(n\) 的序列 \(a\)，满 足 \(1\le a_i \le m\) 且对于任意 \(1\le i < j \le n\) 都满足 \(\gcd(a_i,a_j)=1\)。

\(n\le 10^5,m\le100,T\le 500\)。

数论 + 状压 DP。

其实只要先求所有数都 \(\ge 2\) 的序列方案数，剩下的位置填 \(1\) 即可。

观察到 \(m\) 很小，将 \([2,m]\) 的数的质因子出现的情况可以状压（\(100\) 以内只有二十多个质数）。

进一步地，每个数大于 \(\sqrt{m}\) 的质因子至多有 \(1\) 个，所以只需要把 \(2,3,5,7\) 四个质数压进状态，然后将 \([2,m]\) 所有数按照（大于 \(7\) 的）最大质因子分组。

对于质因子只有 \(2,3,5,7\) 的数，用背包 DP 统计方案数，设 \(f_{i,j,S}\) 表示前 \(i\) 个数中选 \(j\) 个数质因子状态为 \(S\) 的方案数： \[ f_{i,j,S}\leftarrow f_{i-1,j,S}+f_{i-1,j-1,S-p(x)} \] 对于分组后每一组的数，一个状态中至多选一个，同理进行 DP。

注意上界最多选二十多个数，并且第一维可以省去。

然后统计选 \(i\) 个数的方案数为 \(g_i\)，最后答案为： \[ \begin{aligned} &\sum_{i=0}^{\min\{m,30\}}g_i\times i!\times \binom{n}{i}\\ &=n!\times\sum_{i=0}^{\min\{m,30\}} g_i\times \frac{1}{(n-i)!} \end{aligned} \]

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
const int N = 1e5 + 9;
const int M = 109;
const int P = 1e9 + 7;
const int Lim = 1 << 4;

int T, n, m;
int p[M], f[M][20], g[M], fac[N], ifac[N];
int prime[] = { 2, 3, 5, 7 };
vector<int> a[M];

inline void clear() {
    for (int i = 1; i <= m; ++i) a[i].clear();
    memset(p, 0, sizeof p);
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
}

inline void dec() {
    for (int i = 2; i <= m; ++i) {
        int t = i;
        for (int j = 0; j < 4; ++j) {
            int k = prime[j];
            if (t % k) continue;
            p[i] |= 1 << j;
            while (t % k == 0) t /= k;
        }
        a[t].push_back(i);
    }
}

int main() {
    int lm = 1e5;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= lm; ++i) fac[i] = (LL)fac[i - 1] * i % P;
    ifac[lm] = power(fac[lm], P - 2);
    for (int i = lm - 1; i; --i) ifac[i] = (LL)ifac[i + 1] * (i + 1) % P;

    cin >> T;
    while (T--) {
        clear();
        cin >> n >> m;
        dec();
        f[0][0] = 1;
        for (int i = 0; i < (int)a[1].size(); ++i) {
            int x = a[1][i];
            for (int j = 30; j; --j) {
                for (int s = 0; s < Lim; ++s) {
                    if ((s & p[x]) != p[x]) continue;
                    f[j][s] = (f[j][s] + f[j - 1][s ^ p[x]]) % P;
                }
            }
        }
        for (int i = 2; i <= m; ++i) {
            if (a[i].empty()) continue;
            for (int j = 30; j; --j) {
                for (int s = 0; s < Lim; ++s) {
                    for (int k = 0; k < (int)a[i].size(); ++k) {
                        int x = a[i][k];
                        if ((s & p[x]) != p[x]) continue;
                        f[j][s] = (f[j][s] + f[j - 1][s ^ p[x]]) % P;
                    }
                }
            }
        }
        for (int i = 0; i <= 30; ++i) {
            for (int s = 0; s <= Lim; ++s) g[i] = (g[i] + f[i][s]) % P;
        }
        int ans = 0;
        for (int i = 0; i <= min(m, 30); ++i) {
            ans = (ans + (LL)g[i] * ifac[n - i]) % P;
        }
        ans = (LL)ans * fac[n] % P;
        cout << ans << endl;
    }
    return 0;
}