2023 年 2、3 月做题记录

板刷没有太大意义。Codeforces 的真正作用是一个庞大的题库，请善用 Problemset 的标签功能。

打 * 的代表瞄了眼题解，打 ** 的代表压根不会。

第四周

？？？

2.18

开始了！

* [CF1788D] Moving Dots *2000

Portal.

正常来讲会汇聚到一个点，答案为 $2^n-n-1$ 。如果会停留在多个位置，仅当存在一对相邻的点会毅然相背而离，这时候可以统计有多少种情况会使得这两个点是相邻的。发现每存在一对这样的点，答案就会变大一。

$O(n^2\log n)$ 统计即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007; 

int n; 
int a[3005], p[3005]; 

int find(int x) {
    int L = 0, R = n + 1; 
    while (L + 1 != R) {
        int mid = L + R >> 1; 
        if (a[mid] >= x) R = mid; 
        else L = mid;
    }
    return R; 
}

int main(void) {
    scanf("%d", &n); for (int i = p[0] = 1; i <= n; ++i) p[i] = 1ll * p[i - 1] * 2 % P; 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    int res = 0; 
    for (int l = 1; l < n; ++l) for (int r = l + 1; r <= n; ++r) {
        int len = a[r] - a[l]; 
        int x = find(a[l] - len), y = find(a[r] + len) - 1;
        if (x >= l || y <= r) continue; 
        res = (res + 1ll * (p[l - x] - 1) * (p[y - r] - 1) % P * p[x - 1] % P * p[n - y] % P) % P;
    }
    printf("%d\n", ((p[n] - n - 1 + res) % P + P) % P); 
    return 0;
}

[CF1780F] Three Chairs *2300

Portal.

将 $a$ 排序，要求的就是：

$\begin{aligned} ans&=\sum_{1\le i<j\le n} (j-i+1)[\gcd(a_i, a_j)=1]\\ &=\sum_{1\le i<j\le n} (j-i+1)\sum_{d\mid a_i,d\mid a_j}\mu(d)\\ &=\sum_{d}\mu(d)\sum_{1\le i<j\le k} p_j-p_i-1 \end{aligned}$

其中 $p$ 表示是 $d$ 的倍数的数的下标位置。简单转化一下贡献，后面那一坨就是：

$-\frac{k(k-1)} 2+\sum_{i=1}^{k}p_i\times (2i-k-1)$

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int N = 300000; 

int n; 
int a[300005], mu[300005];
int prime[100005], tot, pos[300005], idx[300005]; 
bool v[300005]; 

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    sort(a + 1, a + n + 1); mu[1] = 1; 
    for (int i = 1; i <= n; ++i) pos[a[i]] = i; 
    for (int i = 2; i <= N; ++i) {
        if (!v[i]) prime[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            v[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i]; 
        }
    }
    i64 ans = 0; 
    for (int d = 1; d <= N; ++d) if (mu[d]) {
        int k = 0; 
        for (int i = d; i <= N; i += d) 
            if (pos[i]) idx[++k] = pos[i];
        i64 res = -1ll * k * (k - 1) / 2; 
        for (int i = 1; i <= k; ++i)
            res += 1ll * idx[i] * (2 * i - k - 1);
        ans += mu[d] * res; 
    }
    printf("%lld\n", ans); 
    return 0;
}

2.21

鸽了好几天

** [CF1781F] Bracket Insertion *2700

Portal.

tourist 的神仙题，orz。

采用常见的括号处理方法，设 ( = 1, ) = -1，需要让最小前缀和为 $0$ 。在前缀和 $x$ 后面插入 () 可以得到 $x,x+1,x$ ，插入 )( 可以得到 $x,x-1,x$ 。

前缀和怎么维护？设 $f_{n,x}$ 代表要对前缀和 $x$ 搞 $n$ 次依然合法的方案数，那么：

$f_{n,x}= \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1-i} p \binom{n-1}{i} \binom{n-1-i}{j} f_{i, x} f_{j, x + 1} f_{n - 1 - i - j, x}\\ + \sum\limits_{i=0}^{n-1} \sum\limits_{j=0}^{n-1-i} (1 - p) \binom{n-1}{i} \binom{n-1-i}{j} f_{i, x} f_{j, x - 1} f_{n - 1 - i - j, x}$

利用乘法分配律把 $j$ 相关的东西提出来可以消掉一个求和符号，这样时间复杂度为 $O(n^3)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 998244353;

int poww(int a, int b) {
    int res = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) res = 1ll * res * a % P; 
    return res; 
}
inline void add(i64 &x, i64 t) { x = (x + t) % P; }

int n, p, C[505][505]; 
i64 f[505][505], g[505][505]; 

int main(void) {
    scanf("%d%d", &n, &p); p = 1ll * p * poww(10000, P - 2) % P;
    for (int i = 0; i <= n; ++i) for (int j = C[i][0] = 1; j <= i; ++j) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; 
    for (int i = 0; i <= n; ++i) f[0][i] = g[0][i] = 1; 
    for (int i = 1; i <= n; ++i) 
        for (int x = 0; x <= n; ++x) {
            for (int j = 0; j < i; ++j)
                add(f[i][x], C[i - 1][j] * (p * f[j][x + 1] % P + (1 - p + P) * (x ? f[j][x - 1] : 0) % P) % P * g[i - j - 1][x] % P);
            for (int j = 0; j <= i; ++j)
                add(g[i][x], C[i][j] * f[j][x] % P * f[i - j][x] % P); 
        }
    i64 ans = f[n][0]; 
    for (int i = 1; i <= n * 2; i += 2) ans = ans * poww(i, P - 2) % P; 
    printf("%lld\n", ans); 
    return 0;
}

2.22

为什么我这么摆？？？？？？？？？？？？？？？？啥都不会还摆？？？？？？？？？？？？？？？？？？破大防。

** [CF1591F] Non-equal Neighbours *2400

Portal.

令 $f_{i,0/1}$ 表示将 $a_{1\dots i}$ 划分成偶数/奇数段的方案数，划分成的段要求内部全部相等。那么根据容斥原理，答案为 $(-1)^n (f_{n,0}-f_{n,1})$ 。

转移很简单，枚举当前这一段的左端点即可：

$f_{i,0/1}=\sum_{j=1}^{i}f_{j-1,1/0}\times \min\{a_{j\dots i}\}$

考虑利用 $\min$ 的单调性来优化复杂度。维护一个 $a_i$ 严格递增的单调栈，考虑扫描到 $i$ 时的栈顶在序列中的下标为 $x$ ，那么：

$f_{i,0/1}=f_{x,0/1}+a_i\sum_{j=x+1}^i f_{j-1,1/0}$

因为左端点 $x$ 之后的最小值全是 $a_i$ ，而对于左端点在 $x$ 及前面 $a_i$ 对最小值没有影响，直接就是 $f_{x,0}$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 998244353; 

int n, a[200005], st[200005], tot; 
i64 f[200005][2], s[200005][2]; 

int main(void) {
    scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    f[0][0] = s[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        while (tot && a[st[tot]] >= a[i]) --tot; 
        f[i][0] = ((tot ? f[st[tot]][0] : 0) + (s[i - 1][1] - (tot ? s[st[tot] - 1][1] : 0)) * a[i]) % P;
		f[i][1] = ((tot ? f[st[tot]][1] : 0) + (s[i - 1][0] - (tot ? s[st[tot] - 1][0] : 0)) * a[i]) % P;
        s[i][0] = (s[i - 1][0] + f[i][0]) % P; 
        s[i][1] = (s[i - 1][1] + f[i][1]) % P; 
        st[++tot] = i; 
    }
    printf("%lld\n", (((n & 1) ? -1 : 1) * (f[n][0] - f[n][1]) % P + P) % P);
    return 0;
}

2.23

我死。

** [CF888F] Connecting Vertices *2500

Portal.

可以将多边形展开成一条链，连边时只能覆盖或不交。考虑区间 DP，可以枚举中间的连接点，也可以通过 $[l,r]$ 连接。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;
inline void add(int &x, int t) { x += t; if (x >= P) x -= P; }

int n, a[505][505]; 
int f[505][505][2]; 

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) scanf("%d", &a[i][j]); 
    for (int i = 1; i <= n; ++i) f[i][i][0] = 1; 
    for (int len = 2; len <= n; ++len)
        for (int i = 1; i <= n - len + 1; ++i) {
            int j = i + len - 1; 
            if (a[i][j]) {
                for (int k = i; k < j; ++k) 
                    add(f[i][j][1], 1ll * (f[i][k][0] + f[i][k][1]) * (f[k + 1][j][0] + f[k + 1][j][1]) % P); 
            }
            for (int k = i + 1; k < j; ++k) 
                if (a[i][k]) add(f[i][j][0], 1ll * f[i][k][1] * (f[k][j][0] + f[k][j][1]) % P); 
        }
    printf("%d\n", (f[1][n][0] + f[1][n][1]) % P); 
    return 0;
}

2.24

我怎么什么都不会。

** [CF840C] On the Bench *2500

Portal.

首先乘积为完全平方数有类似与传递性的性质，因此可以将数分为 $m$ 组，第 $i$ 组的数字个数为 $s_i$ 。

设 $f_{i,j}$ 代表考虑前 $i$ 个组，有 $j$ 个相邻数乘积为完全平方数的对。可以将第 $i$ 个组分成 $k$ 个连续段（这一部分的方案数可以预处理），不合法的数量会增加 $s_i-k$ ，然后选择破坏掉之间 $j$ 个相邻中的 $l(0\le l\le k)$ 个，这样 $f_{i-1,j}$ 转移到了 $f_{i,j+s_i-k-l}$ 。在 $j$ 中选择 $l$ 个破坏掉会使用这一组中的 $l$ 段，还剩 $k-l$ 段选择插入在剩下的 $sum+1-j$ 个空中即可（ $sum=\sum_{p=1}^{i-1}s_i$ ）。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 1000000007; 

int n, m, cnt[305], p[305]; 
int a[305]; 
int C[305][305]; 
int f[305][305], g[305][305]; 
inline void add(int &x, int t) { x += t; if (x >= P) x -= P; }
// g[i][j] : 将 i 个不同的数分成 k 个连续段落

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i); bool flag = 0; 
        for (int j = 1; j <= m; ++j) {
            i64 u = 1ll * p[j] * a[i], v = sqrt(u); 
            if (v * v == u) { ++cnt[j]; flag = 1; break; }
        }
        if (!flag) p[++m] = a[i], cnt[m] = 1; 
    }
    for (int i = 0; i <= n; ++i) 
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P; 
    f[0][0] = 1, g[0][0] = 1; 
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j)
        g[i][j] = (1ll * g[i - 1][j] * (i - 1 + j) + 1ll * g[i - 1][j - 1] * j) % P;
    int sum = 0; 
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= sum; ++j) for (int k = 1; k <= cnt[i]; ++k) for (int l = 0; l <= k; ++l)
            add(f[i][j + (cnt[i] - k) - l], 1ll * f[i - 1][j] * g[cnt[i]][k] % P * C[j][l] % P * C[sum + 1 - j][k - l] % P);   
        sum += cnt[i];
    }
    printf("%d\n", f[m][0]); 
    return 0;
}

2.28

哼哼，这都要 NOIP 了。

[CF1779F] Xorcerer’s Stones *2500

Portal.

拍成 DFS 序在序列上做。从根往子树进行操作（否则交换也可），所以设 $f_{i,j}$ 代表考虑到 $[1,i-1]$ 的选择情况，当前的异或和为 $j$ ，记录从哪里来的和异或值。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n; 
int sum[200005], siz[200005], idx[200005], num; 
vector<int> G[200005]; 
pair<int, int> f[200005][32];

void dfs(int x) {
    idx[++num] = x; siz[x] = 1; 
    for (int y : G[x]) dfs(y), siz[x] += siz[y], sum[x] ^= sum[y]; 
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", sum + i); 
    for (int i = 2; i <= n; ++i) {
        int f; scanf("%d", &f); 
        G[f].emplace_back(i); 
    } dfs(1); 
    memset(f, -1, sizeof f); f[1][sum[1]] = {0, 0}; 
    for (int i = 1; i <= n; ++i) for (int j = 0; j < 32; ++j) if (f[i][j].first != -1) {
        int v = (siz[idx[i]] & 1) ? 0 : sum[idx[i]]; 
        f[i + 1][j] = {i, j};
        f[i + siz[idx[i]]][j ^ v] = {i, j}; 
    }
    if (f[n + 1][0].first == -1) return puts("-1"), 0;
    vector<int> ans; 
    int u = n + 1, v = 0; 
    while (u) {
        int tu = f[u][v].first, tv = f[u][v].second; 
        if (u - tu == siz[idx[tu]]) ans.emplace_back(idx[tu]); 
        u = tu, v = tv; 
    } ans.emplace_back(1); 
    printf("%d\n", ans.size());
    for (int x : ans) printf("%d ", x); putchar('\n'); 
    return 0;
}

* [CF1733E] Conveyor *2700

Portal.

谔谔题。便谔谔地开始想。

显然两只史莱姆不会变成大史莱姆。因为距离都不一样。

这样求出 $t$ 时刻内所有经过 $x,y$ 的史莱姆是容易计算的。发现经过 $(x,y)$ 的 $a$ 史莱姆有 $\left\lceil\frac a 2 \right\rceil$ 走到 $(x,y+1)$ ， $\left\lfloor\frac a 2 \right\rfloor$ 走到 $(x+1,y)$ 。

似乎可以递推！但是注意初始时 $f_{0,0}=t-x-y+1$ 。因为在这个时刻开始，新出生的史莱姆就到不了 $(x,y)$ 。

这样差分，看 $t-1$ 和 $t$ 时刻经过 $(x,y)$ 的史莱姆个数，相等的话就没有史莱姆在 $t$ 时刻出现在 $(x,y)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 1000000007;

i64 t, f[125][125]; int x, y; 
i64 calc(i64 t, int x, int y) {
    if (x + y > t) return 0; 
    memset(f, 0, sizeof f); 
    f[0][0] = t - x - y + 1; 
    for (int i = 0; i < 120; ++i)
        for (int j = 0; j < 120; ++j) {
            f[i][j + 1] += f[i][j] + 1 >> 1; 
            f[i + 1][j] += f[i][j] >> 1; 
        }
    return f[x][y]; 
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%lld%d%d", &t, &x, &y); 
        if (t == 0) puts(x == 0 && y == 0 ? "YES" : "NO");
        else puts(calc(t - 1, x, y) == calc(t, x, y) ? "NO" : "YES"); 
    }
    return 0;
}

3.1

我谔谔。

* [CF1774F2] Magician and Pigs *2700

Portal.

非常有趣。

考虑复制操作是干了什么。新生成的猪和原来的猪是一样的，但原来的猪还要再受到一遍伤害打击。所以说，相当于复制操作会克隆出当前所有的猪，然后让克隆猪再承受一遍前面受到的伤害。

这样可以处理出每个复制操作前面所附带的伤害，然后倒序扫描。对于每一头猪，先减掉它后面会被扣去的血量。然后从后往前扫描所有的复制操作看其是否可以进行。如果这头猪可以吃得住这个复制操作打出的伤害，那么这个复制操作之前的所有复制操作所克隆出的猪都是可以存活到最后的。然后猪的血量要减去这个伤害（接下来求解的就是当前复制操作的克隆猪了）。

时间复杂度 $O(n\log V)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int P = 998244353; 
const i64 S = 1000000000;

int n, tot; 
int a[800005]; i64 b[800005], c[800005]; 

int main(void) {
    scanf("%d", &n); i64 sum = 0, ans = 0; 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i); if (a[i] != 3) scanf("%lld", b + i); 
        if (a[i] == 2) sum = min(sum + b[i], S); 
        if (a[i] == 3) b[i] = sum, sum = min(sum * 2, S); 
    } sum = 0; i64 res = 1; 
    for (int i = n; i >= 1; --i) {
        if (a[i] == 1) {
            b[i] -= sum; // 扣掉后面操作附加的真伤
            if (b[i] <= 0) continue; 
            i64 r = b[i], cnt = 1; // 原本会有一只，就是一个复制操作都不进行
            for (int j = 1; j <= tot; ++j) // 看能够复制到哪里
                if (r > c[j]) {
                    cnt = (cnt + (1ll << tot - j)) % P; // 进行第 j 个复制操作
                    r -= c[j]; 
                }
            ans = (ans + res * cnt) % P; 
        } else if (a[i] == 2) sum += b[i]; 
        else {
            if (b[i] == S) continue; // 毁灭打击，克隆的猪都死
            if (b[i] == 0) { res = res * 2 % P; continue; } // 无伤害，猪翻倍
            c[++tot] = b[i]; 
        }
    }
    printf("%lld\n", ans); 
    return 0;
}

* [CF1762E] Tree Sum *2600

Portal.

设连接 $i$ 的边权为 $d_i$ ，而每条边对 $\prod d_i$ 的贡献为 $1$ ，然而 $n$ 为奇数时 $\prod d_i=-1$ 永远不可能满足，因此 $n$ 为奇数时无解。

如果 $n$ 为偶数且树的形态固定，那么参考 Prufer 序列的构造方式，从叶子开始赋予边权，那么方式一定是唯一的！也就是说，对于给定的树的形态只有一种方式。

这样的话，一条边 $(u,v)$ 的权值为 $1$ 的充要条件是：断掉这条边之后两个连通块大小均为偶数。因为这样两个连通块都满足条件了，这条边填 $1$ 即可。

考虑逐边计算贡献，枚举 $1$ 所在的连通块大小 $i$ ，这样 $n$ 所对应的连通块大小便为 $n-i$ 。

此时这条边的边权为 $(-1)^i$ 。
剩下 $n$ 个点中随便扔，方案数为 $\binom{n-2}{i-1}$ 。
两块随便制造无根树，根据 Cayley 公式计算即可。
随便找两个点连接。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353; 

int poww(int a, int b) {
    int res = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) res = 1ll * res * a % P; 
    return res; 
}

int n; 
int fac[500005], ifac[500005]; 

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

int f(int n) {
    if (n == 1) return 1; 
    return poww(n, n - 2); 
}

int main(void) {
    scanf("%d", &n); 
    if (n & 1) return puts("0"), 0; 
    for (int i = fac[0] = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % P; 
    ifac[n] = poww(fac[n], P - 2); 
    for (int i = n - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
    int ans = 0; 
    for (int i = 1; i < n; ++i)
        ans = (ans + (i & 1 ? -1ll : 1ll) * i * (n - i) % P * C(n - 2, i - 1) % P * f(i) % P * f(n - i) % P) % P; 
    printf("%d\n", (ans % P + P) % P);  
    return 0;
}

3.3

最后的挣扎。

** [CF1626F] A Random Code Problem *2800

Portal.

实际上求的是所有数的和。

我们只关心前 $k-1$ 轮操作数被减去了多少，因此将数对 $L=\operatorname{lcm}(0\sim k-1)$ 取模后减去的值是等价的。

初始时我们令所有数都要减去它们会减去的值，每个数会被选 $k\times n^{k-1}$ 次。

开始 DP！设 $f_{i,j}$ 表示进行 $j$ 轮后模 $L$ 等于 $i$ 的数的个数。每次给答案加上没有减去的贡献，然后更新有多少个数。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353; 

int n, a[10000005], x, y, k, M, L = 1; 
int f[10000005], p[20]; 
int ans; 

int main(void) {
    cin >> n >> a[0] >> x >> y >> k >> M; 
    for (int i = p[0] = 1; i <= k; ++i) p[i] = 1ll * p[i - 1] * n % P; 
    for (int i = 1; i < k; ++i) L = L / __gcd(L, i) * i; 
    for (int i = 0; i < n; ++i) {
        if (i) a[i] = (1ll * a[i - 1] * x + y) % M; 
        ans = (ans + 1ll * (a[i] / L * L) * k % P * p[k - 1] % P) % P; 
        ++f[a[i] % L]; 
    }
    for (int i = 1; i <= k; ++i)
        for (int j = 0; j < L; ++j) {
            int c = f[j]; 
            ans = (ans + 1ll * c * j % P * p[k - i] % P) % P; // 加上减去的贡献
            f[j] = 1ll * c * (n - 1) % P; 
            f[j - j % i] = (f[j - j % i] + c) % P; 
        }
    printf("%d\n", ans); 
    return 0;
}

3.4

NOIP 死了，省选需要多考 50+ 分。

[CF955C] Sad powers *2100

Portal.

呆呆题。这是原题。气死人，为什么我平时不多刷点题！！！

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const i64 N = 1e18; 

int tot; 
i64 num[30000005];

int calc(i64 n) {
    int idx = lower_bound(num + 1, num + tot + 1, n) - num;
    if (idx > tot || (idx <= tot && num[idx] > n)) --idx; 
    return idx + sqrt(n); 
}

int main(void) {
    for (i64 i = 2; i <= 1000000; ++i) {
        i64 k = i * i; 
        for (; k <= N / i; ) {
            k *= i; i64 sq = sqrt(k); 
            if (sq * sq != k) num[++tot] = k;
        }
    }
    sort(num + 1, num + tot + 1); 
    tot = unique(num + 1, num + tot + 1) - (num + 1);  
    int T; i64 l, r; scanf("%d", &T); 
    while (T--) {
        scanf("%lld%lld", &l, &r); 
        printf("%d\n", calc(r) - calc(l - 1)); 
    }
    return 0;
}

[CF316D3] PE Lesson *2400

Portal.

呆呆题。如果只能交换一次可以简单 DP，交换两次可以变成任意一个人。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;

int n, cnt;
int f[1000005];

int main(void) {
    scanf("%d", &n); 
    for (int i = 1, x; i <= n; ++i) scanf("%d", &x), cnt += (x == 1); 
    f[0] = f[1] = 1; 
    for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + 1ll * (i - 1) * f[i - 2]) % P; 
    int ans = f[cnt]; 
    for (int i = n; i > cnt; --i) ans = 1ll * ans * i % P; 
    printf("%d\n", ans); 
    return 0;
}

？？？

不知道。

3.20

不知道。

[SNOI2022] 倍增

Portal.

如果构造出来了一个答案，那么只需要在进位的地方后面填 $B-1$ 即可。

枚举答案的长度、 $2\times a_i$ 对应 $a_{p_i}$ 、每一位是否进位，这样在置换 $p$ 上形成的环所构成的方程组可以解出来。

查看代码

#include <bits/stdc++.h>
using namespace std;

int ans[200005]; 
vector<int> ans0[200005], ans1[200005]; 

void solve(int B) {
    int p[20], w[20]; bool vis[20]; 
    for (int n = 2;; ++n) {
        // 2(a[n] a[n-1] a[1]) = (a[p[n]], a[p[n-1]], a[p[1]])
        for (int i = 1; i <= n; ++i) p[i] = i; 
        do {
            for (int s = 2; s < 1 << n; s += 2) { // 必须有一个进位
                for (int i = 1; i <= n; ++i) w[i] = -1, vis[i] = 0; 
                for (int i = 1; i <= n; ++i) if (!vis[i]) {
                    int a[20] = {0}, wx[20] = {0}, wy[20] = {0}, m = 0; 
                    for (int j = i; !vis[j]; j = p[j]) vis[a[++m] = j] = 1;
                    wx[1] = 1; wy[1] = 0; 
                    for (int j = 2; j <= m; ++j) {
                        wx[j] = wx[j - 1] * 2; 
                        wy[j] = wy[j - 1] * 2 + (s >> a[j - 1] - 1 & 1) - B * (s >> a[j - 1] & 1); 
                    }
                    wx[1] = wx[m] * 2 - 1; 
                    wy[1] = wy[m] * 2 + (s >> a[m] - 1 & 1) - B * (s >> a[m] & 1); 
                    if (wy[1] % wx[1] != 0) continue; 
                    w[a[1]] = -wy[1] / wx[1]; 
                    for (int j = 2; j <= m; ++j) w[a[j]] = wx[j] * w[a[1]] + wy[j];
                }
                bool flag = 1; 
                for (int i = 1; i <= n; ++i) flag &= (0 <= w[i] && w[i] < B); 
                if (flag) {
                    ans[B] = n; 
                    for (int i = 1; i <= n; ++i) if (s >> i & 1) {
                        for (int j = n; j > i; --j) ans0[B].emplace_back(w[j]);
                        for (int j = i; j >= 1; --j) ans1[B].emplace_back(w[j]); 
                        return;  
                    }
                }
            }
        } while (next_permutation(p + 1, p + n + 1)); 
    }
}

int main(void) {
    int T, n, B; scanf("%d", &T); 
    while (T--) {
        scanf("%d%d", &n, &B); 
        if (!ans[B]) solve(B);
        if (ans[B] > n) { puts("-1"); continue; }
        vector<int> A; 
        for (int x : ans0[B]) A.emplace_back(x); 
        for (int i = 0; i < n - ans[B]; ++i) A.emplace_back(B - 1); 
        for (int x : ans1[B]) A.emplace_back(x); 
        for (int x : A) printf("%d ", x); 
        putchar('\n'); 
    }
    return 0;
}

3.21

也不知道。

[ARC117E] Zero-Sum Ranges 2

Portal.

容易想到在前缀和序列上进行思考。设 $c_i$ 代表 $i$ 在前缀和序列中的出现次数，那么答案为 $\sum_{i}\binom{c_i}{2}$ 。

按照前缀和从大到小的顺序（人类智慧）开始放置，设 $f_{i,j,k}$ 代表当前放了 $i$ 个数，答案是 $k$ ，有 $j$ 个洞（下一层有 $j+1$ 个需要放）。枚举当前层放置几个，转移很显然。

计算答案的时候需要合并正负前缀和。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int N = 62; 
inline void add(i64 &x, i64 t) { x += t; }

int n, s; 
i64 C[65][65]; 
i64 f[65][65][3605]; 

int main(void) {
    for (int i = 0; i <= N; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; 
    scanf("%d%d", &n, &s); 
    for (int i = 1; i <= n + 1; ++i) f[i][i - 1][i * (i - 1) / 2] = 1; 
    for (int i = 1; i <= n * 2 + 1; ++i) {
        int t = min(i * (i - 1) / 2, s); 
        for (int j = 0; j <= i; ++j) for (int k = 0; k <= t; ++k) if (f[i][j][k]) {
            for (int x = j + 2; x <= n * 2 + 1 - i; ++x) // 下一层放置 x 个
                add(f[i + x][x - (j + 2)][k + x * (x - 1) / 2], f[i][j][k] * C[x - 1][j + 1]);
        }
    }
    i64 ans = f[n * 2 + 1][0][s];
    for (int i = 2; i <= n * 2 + 1; ++i) 
        for (int j = 1; j <= n + 1; ++j)
            for (int k = 0; k <= s; ++k)
                ans += f[i][j][k] * f[n * 2 + 1 - i][j - 1][s - k]; 
    printf("%lld\n", ans); 
    return 0;
}

3.23

休闲之余做一点奇怪的（这一天开始了 2020 集训队作业）。

[AGC001B] Mysterious Light

Portal.

先照一次之后就是平行四边形，直接递归即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 

i64 ans; 
void calc(i64 n, i64 x) {
    if (n % x == 0) return ans += n * 2 - x, void();
    ans += (n - n % x) * 2; calc(x, n % x);
}

int main(void) {
    i64 n, x; cin >> n >> x; 
    ans = n; n -= x; calc(max(n, x), min(n, x)); 
    cout << ans << "\n"; 
    return 0;
}

[AGC001C] Shorten Diameter

Portal.

按照直径的奇偶性枚举点或边即可。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, k, ans = 1e9, cnt; 
bool vis[2005], vis2[2005], *v; 
vector<int> G[2005]; 
vector<pair<int, int>> E;

void dfs(int x, int dis, int len) {
    if (dis > len) return; ++cnt; v[x] = 1; 
    for (int y : G[x]) if (!v[y]) dfs(y, dis + 1, len); 
}

int main(void) {
    scanf("%d%d", &n, &k); 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); E.emplace_back(u, v);
        G[u].emplace_back(v); G[v].emplace_back(u); 
    }   
    if (k % 2 == 0) {
        for (int i = 1; i <= n; ++i) {
            v = vis; memset(vis, 0, sizeof vis); dfs(i, cnt = 0, k / 2); 
            ans = min(ans, n - cnt); 
        }
    } else {
        for (auto [x, y] : E) {
            v = vis; memset(vis, 0, sizeof vis); dfs(x, 0, k / 2); 
            v = vis2; memset(vis2, 0, sizeof vis2); dfs(y, 0, k / 2); 
            cnt = 0; 
            for (int i = 1; i <= n; ++i) cnt += vis[i] | vis2[i]; 
            ans = min(ans, n - cnt); 
        }
    }
    return printf("%d\n", ans), 0;
}

3.25

？？？

[AGC001D] Arrays and Palindrome

Portal.

出现两个以上的奇数无解，否则错位一下就行。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, t; 
int a[100005], b[100005], cnt[2]; 

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= m; ++i) scanf("%d", a + i), ++cnt[a[i] & 1]; 
    if (cnt[1] > 2) return puts("Impossible"), 0; 
    if (m == 1) {
        if (a[1] == 1) printf("1\n1\n1\n"); 
        else printf("%d\n2\n1 %d\n", a[1], a[1] - 1); 
        return 0; 
    }
    sort(a + 1, a + m + 1, [&](int x, int y) { return x % 2 > y % 2; });
    printf("%d ", a[1]); 
    for (int i = 3; i <= m; ++i) printf("%d ", a[i]); 
    printf("%d\n", a[2]);

    b[++t] = a[1] + 1;
    for (int i = 3; i <= m; ++i) b[++t] = a[i]; 
    if (a[2] > 1) b[++t] = a[2] - 1; 
    
    printf("%d\n", t); 
    for (int i = 1; i <= t; ++i) printf("%d ", b[i]); putchar('\n');
    return 0;
}

[AGC001E] BBQ Hard

Portal.

可以抽象成 $(0,0)\rightarrow(a_i+a_j,b_i+b_j)$ ，也就是 $(-a_i,-b_i)\rightarrow(a_j,b_j)$ ，就可以直接统计了。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int P = 1000000007;
const int D = 2010, N = 10000; 

int poww(int a, int b) {
    int r = 1; 
    for (; b; b >>= 1, a = 1ll * a * a % P) if (b & 1) r = 1ll * r * a % P; 
    return r; 
}

int n; 
int a[200005], b[200005]; 
int fac[10005], ifac[10005], f[4100][4100]; 
int C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P; }

int main(void) {
    for (int i = fac[0] = 1; i <= N; ++i) fac[i] = 1ll * fac[i - 1] * i % P; 
    ifac[N] = poww(fac[N], P - 2);
    for (int i = N - 1; i >= 0; --i) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P; 

    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", a + i, b + i), ++f[D - a[i]][D - b[i]];
    for (int i = 1; i <= D * 2; ++i) for (int j = 1; j <= D * 2; ++j)
        f[i][j] = (f[i][j] + f[i - 1][j] + f[i][j - 1]) % P; 
    int ans = 0; 
    for (int i = 1; i <= n; ++i) {
        ans = (ans + f[D + a[i]][D + b[i]]) % P; 
        ans = (ans - C((a[i] + b[i]) * 2, a[i] * 2)) % P; 
    }
    printf("%lld\n", (1ll * ans * poww(2, P - 2) % P + P) % P);
    return 0;
}

3.26

To the crazy ones, wish us good luck.

[CF1542E2] Abnormal Permutation Pairs (hard version)

Portal.

对于第一条限制，我们设相同前缀的长度为 $L$ ，则 $p_{L+1}<q_{L+1}$ 。后面的贡献统计出来之后，前面显然是可以随意排的。

设 $f_{i,j}$ 代表 $i$ 阶排列， $p$ 的逆序对数减去 $q$ 的逆序对数为 $j$ 时的方案数。设当前要填 $p_1$ 和 $q_1$ 在 $i-1$ 阶排列的首位，转移是容易的：

$f_{i,j}=\sum_{p_1=1}^i\sum_{q_1=1}^i f_{i-1,j-p_1+q_1}$

实际上我们只关心 $p_1-q_1$ 的值，因此枚举 $d=p_1-q_1$ ：

$f_{i,j}=\sum_{|d|<i} f_{i-1,j-d} (i-|d|)$

拆开后发现维护 $f_{i,j}$ 和 $j\times f_{i,j}$ 关于 $j$ 的前缀和即可。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int N = 505, D = N * (N - 1) / 2; 

int n, M; 
int C[N][N], fac[N]; 
int A(int n, int m) { return 1ll * C[n][m] * fac[m] % M; }
i64 f[D * 2 + 10], s1[D * 2 + 10], s2[D * 2 + 10];

int main(void) {
    cin >> n >> M; f[D] = 1; 
    for (int i = 0; i <= n; ++i)
        for (int j = C[i][0] = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M; 
    for (int i = fac[0] = 1; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % M; 
    i64 ans = 0; 
    for (int i = 2; i <= n; ++i) { // i 阶排列
        int lim = i * (i - 1) / 2; i64 c = 0;  
        for (int j = D - lim - i; j <= D + lim + i; ++j)
            s1[j] = (s1[j - 1] + f[j]) % M, s2[j] = (s2[j - 1] + 1ll * f[j] * j % M) % M; 
        for (int j = D - lim; j <= D + lim; ++j) {
            f[j] = (1ll * (s1[j + i] - s1[j]) * (i + j) % M - s2[j + i] + s2[j]) % M; 
            if (j > D) c = (c + f[j]) % M; 
        }
        ans = (ans + 1ll * c * A(n, n - i) % M) % M; 
        for (int j = D - lim; j <= D + lim; ++j)
            f[j] = (f[j] + 1ll * ((s1[j] - s1[j - i]) * (i - j) % M + s2[j] - s2[j - i])) % M; 
    }
    return printf("%lld\n", (ans % M + M) % M), 0;
}