Codeforces Round#717 div.2 回顾

七海

题解

发布于：2021年4月24日

次浏览

记录

比赛的那天 KS 酱办生日聚会，所以玩的有点晚——于是为了避免掉分就又开了个小号——结果还真的算是预防成功了（（只能说不愧是我==

和上一场一样的出题人，也是熟悉的五个题目；但是这场总感觉比之前那一场要难一些——可能出题人不经意间触及了我较多的知识盲区吧（

题解

A - Tit for Tat

右手就行~~可是我白给了一发~~；只要取出前面的加到最后一个元素上就行了：

const int N = 100;
int a[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int T = $.nextInt(), n, k;
    while (T --) {
        input, n, k;
        $.nextArray(a + 1, a + 1 + n);
        int l = 1, r = n;
        while (k && l < r) {
            auto ded = min(k, a[l]);
            k -= ded, a[l] -= ded, a[r] += ded;
            ++ l;
        }
        $.putArray(a + 1, a + 1 + n);
    }

    return 0;
}

到底是什么样的小天才才能写出 ++ l, -- r 这种代码呢？以为很对称🐎（

C - Baby Ehab Partitions Again

提供长度为 \(n \leq 100\) 的数组 \(a\)，你要从中删除一些元素，使得不可以将这个数组拆分成两个部分，使得两个部分的和相等；要求最小化删除元素的数量并输出删除元素的坐标。

首先，显然当 \(\sum_{i = 1}^n a_i\) 是奇数的时候不用删除任何元素；然后，为偶数情况下可以进行背包 \(DP\) 来判断是否可能完成这样的划分；如果可以，那么问题就变成了如何删除元素。

不难想到最多只会删除一个元素，那么问题就是删除什么样的元素；我最开始因为删除最小的元素然后白给了一些罚时，因为这样是不正确的——比如删除 2，可以通过交换两个 2 和一个 5 来使得再次平衡；那么我们在考虑其他的一定可行的情况，就不难想到删除一个奇数。

如果整个数组都是偶数怎么办？那么我们可以整体右移 \(1\) 位，显然和原数组是等价的；我们可以一直右移，直到我们找到了可以删除的奇数为止；显然，这一定可以找到；

从右移等价，我们可以联想到整个数组除以任何同一个数都是等价的；所以，一个最简单的方法就是首先约去整个数组的 \(\gcd\)，然后找到一个奇数删除就行了——因为是等价的，所以这样的删除是合理的；

代码实现

这个使用 bitset 的可行性背包实现属实颇有雅趣（

const int N = 2050, M = 110;
int a[N];
 
bool check(int n) {
    int sum = accumulate(a + 1, a + 1 + n, 0);
    if (sum % 2) return false;
    bitset<N * M> dp;
    dp.set(0);
    for (int i = 1; i <= n; ++ i)
        dp |= (dp << a[i]);
    return dp[sum / 2];
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);
 
    int n = $.nextInt();
    $.nextArray(a + 1, a + 1 + n);
    if (check(n)) {
        int g = 0;
        for (int i = 1; i <= n; ++ i)
            g = gcd(g, a[i]);
        for (int i = 1; i <= n; ++ i)
            if (a[i] / g % 2) {
                $.put(1).put(i);
                break;
            }
    } else $.put(0);
 
    return 0;
}

于是这个卵题我白给了近十发，，我是真的菜（

D - Cut

给一个长度为 \(n \leq 10^5\) 的数组 \(a\)，进行 \(q\leq10^5\) 次询问：每次询问关于一个区间 \([l, r]\)，将它分成的最少的段数，使得每一段的 \(\text{LCM}\) 都和连乘的乘积相等；求这个段数。

首先，不难意识到 \(\text{LCM}\) 和连乘积相等就是说这一段的 \(\gcd\) 为 \(1\)。那么问题就转化为了对于任意段 \([l, r]\)，将它划分成互质的最小的段数。

那么一种很显然的想法就是对于范围内的所有质数（约 \(9600\) 个）分别维护一个列表，包含了包含它为质因数的数字的下标；然后对于一个位置，对于它的每一个质因子在对应的表上二分查找出下一个位置，取最小值作为下一个区间开始的备选位置；但是这样做显然非常的啥b，因为有显而易见地简单优化~~但是我也显而易见的没有想到~~：

我们可以倒着维护每一个质数的下一个位置，这样就不用对每个质数二分查找了
倒着转移的时候也考虑后一个位置的备选位置，这样就不用考虑到备选区间之间的冲突了

那么这样，我们就可以维护出一个表 \(F_i\)，表示从 \(i\) 开始可以转移到的最远的备选位置；

但是这样还存在一个问题：如果所有的数字都是 \(1\)，那么上面的做法会被卡成 \(n^2\)；因此，为了能够快速的跳转求出区段数，我们可以利用倍增的思想，维护下两个、下四个备选位置；这样，就可以在 \(\log n\) 的时间内完成转移，并且像二进制拆位那样构造出任何一个数字。

代码实现

使用类筛的方法完成质因数分解。

const int N = 1e5 + 5;
const int M = 9600;
int a[N], f[20][N], to[M];

auto decomposition(const int n) {
    static vector<int> p;
    static vector<vector<int>> de(n);
    for (int i = 2; i < n; ++i)
        if (de[i].empty()) {
            for (int j = i; j < n; j += i)
                de[j].push_back(i);
            p.push_back(i);
        }
    return make_pair(ref(p), ref(de));
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n, q, l, r;
    $(n, q).nextArray(a + 1, a + 1 + n);
    auto [p, de] = decomposition(N);

    unordered_map<int, int> desc;
    const auto ps = p.size();
    const auto bound = n + 1;
    desc.reserve(ps * 4);
    for (int i = 0; i < ps; ++ i) {
        desc[p[i]] = i, to[i] = bound;
    }

    f[0][bound] = bound;
    for (int i = n; i; -- i) {
        f[0][i] = f[0][i + 1];
        for (auto j : de[a[i]]) {
            minimize(f[0][i], to[desc[j]]);
            to[desc[j]] = i;
        }
    }
    for (int i = 1; i < 20; ++ i)
        for (int j = 1; j <= bound; ++ j)
            f[i][j] = f[i - 1][f[i - 1][j]];

    while (q --) {
        $(l, r);
        uint ans = 0;
        for (int i = 19; i >= 0; -- i)
            if (f[i][l] <= r) {
                ans += (1u << i);
                l = f[i][l];
            }
        $.put(ans + 1);
    }

    return 0;
}

即使可以想到正确的维护方法，但是倍增的思想也不能不说是十分的高妙…… 学到许多（

E - Baby Ehab Plays with Permutations

现在有长度为 \(n \leq 10^9\) 的排列 \(\{1, \dots,n\}\)，可以进行对于两个不同的下标两两交换的操作 \(k \leq 200\) 次；问对于 \([1, k]\) 次操作可以得到的不同的排列数量；

首先，先说明一种贪心地将长度为 \(n\) 的排序 \(p\) 复位的做法——对于排列的最后一个位置 \([n]\)：

如果 \(p_n = n\)，那么可以忽略这个位置；将原排列看作长度为 \(n - 1\)
否则，将 \(p_n\) 和 \(p_{p_n}\) 交换位置；此时至少可以使得 \(p_n\) 复位，继续递归，但是操作次数 \(+1\)

可以证明，这样处理完整个序列就可以得到将序列 \(p\) 复位的最小操作次数。

那么，基于这种思想，我们可以构造出一种递推关系——假设 \(F_{n, j}\) 表示了进行 \(j\) 次交换后可以复位的、长度为 \(n\) 的排列（或者说从复位的排列开始，进行 \(j\) 次交换可以产生的排列）的数量：

\(j = 0\)：此时，只有初始复位的排列一种情况；因此总是为 \(1\)
现在，我们考虑通过 \(F_{n - 1}\) 向 \(F_n\) 转移；即每次将 \(n\) 放入长度为 \(n - 1\) 的排列中：
- 如果新放入的 \(n\) 不进行交换，那么对答案没有贡献：可以直接转移
- 如果和前面的 \(n - 1\) 个位置中的一个进行交换：那么贡献 \(1\) 次次数，有 \(n - 1\) 种转移方法
综上所述，可以得到递推公式 \(F_{n, j} = F_{n - 1, j} + (n - 1) \cdot F_{n - 1, j - 1}\)；

那么，基于这个动态规划，我们可以有两种不同的做法：

阳间做法

注意到题目中的 \(k\) 非常的小，所以即使进行 \(k\) 次交换，最多只会使得 \(2k\) 个位置错位；所以我们每次只需要能选出错位的位置长度，然后对于在这个范围内的长度求 \(F_{n, j}\) 即可；那么，一种很显然的做法就是确定一个允许的错位位置的长度 \(i\)，对于这个长度求 \(F\)，最后统一考虑——

那么，答案长下面这样吗？ \[ \text{ans?}_{j} = \sum_{i = 0}^{\min(2j, n)} \mathbf{C}_n^{i} \times F_{i, j} \] 不，当然不对——因为我们的 \(F_{n, j}\) 可能实际上只变动了其中很少一部分的位置——而这样的话就会不可避免的和其他情况重合，导致计数的不准确；所以为了解决这个问题，我们可以考虑在错排问题种采用的解决方法——使用容斥原理包含/排除重复的部分：

现在，我们定义 \(G_{n, j}\) 和 \(F_{n, j}\) 类似，但是每一个位置都是错排的情况数量
然后，我们在 \(F_{n, j}\) 中选择一个位置固定，然后剩下的位置的任何排序就都符合要求，需要排除
但是这样的话，就会导致两个位置固定的情况被多排除了一次，需要重新包含
……

所以，我们就可以在 \(\mathcal{O}(k^2)\) 的时间内完成一次 \(G\) 的求解；算法总复杂度是 \(\mathcal{O}(k^3)\)。

代码实现

一个很容易注意到的事情就是 \(\text{ans}_i\) 可以由 \(\text{ans}_{i - 2}\) 转移过来——因为你可以连续两次进行相同的交换来浪费两次交换机会== 由此，也很容易联想到奇偶分开（

const int N = 500;
const int mod = 1e9 + 7;
longs inv[N], c[N][N], f[N][N];

void initInverse(int n, longs p) {
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
    inv[0] = 0;
}

longs nCr(int n, int r) {
    longs ret = 1;
    for (int i = n - r + 1; i <= n; ++ i)
        ret = ret * i % mod;
    for (int i = 1; i <= r; ++ i)
        ret = ret * inv[i] % mod;
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);
    
    int n = $.nextInt(), k = $.nextInt();
    c[0][0] = 1;
    for (int i = 1; i <= 2 * k; ++ i) {
        f[i][0] = 1, c[i][0] = 1;
        for (int j = 1; j <= 2 * k; ++ j) {
            f[i][j] = (f[i - 1][j] + (i - 1) * f[i - 1][j - 1]) % mod;
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
        }
    }
    initInverse(2 * k, mod);
    longs ans[] = {1, 0};
    vector<int> out;
    for (int j = 1; j <= k; ++ j) {
        const auto lim = min(n, 2 * j);
        for (int i = 1; i <= lim; ++ i) {
            longs cnt = 0, fix, fl;
            for (fix = 0, fl = 1; fix <= i; ++ fix, fl = -fl) {
                cnt = cnt + fl * c[i][fix] * f[i - fix][j] % mod;
                do cnt = (cnt + mod) % mod; while (cnt < 0);
            }
            ans[j % 2] = (ans[j % 2] + nCr(n, i) * cnt) % mod;
        }
        out.push_back((int) ans[j % 2]);
    }
    $.putArray(out.begin(), out.end());

    return 0;
}

一些说明：很显然 \(\mathbf{C}_i^j = \mathbf{C}_{i - 1}^j + \mathbf{C}_{i - 1}^{j - 1}\)；

阴间做法

首先，我们需要先观察上面得到的那个递推公式，并考虑更深刻的理解它：

考虑到 \(F_{n, 0} = 1\)，除了递推的转移引入之外，都是通过 \(n - 1\) 的形式引入的；
什么情况下会引入 \(n - 1\)？当新加入的 \(n\) 不放在 \([n]\) 而是参与了与前面的位置交换的场合下；
引入时产生了什么副作用？因为进行了交换，所以奉献了一次交换次数，\(j = j + 1\)；
所以，我们可以将 \(F_{n, j}\) 看作从“下标”集合 \([0, n - 1]\) 中选出一个大小 \(j\) 的子集求积后求和的结果；

形式化的说，我们可以得到下面的 \(F_{n, j}\) 的表示形式： \[ F_{n, j} = \sum_{s \subset [0, n - 1] \and |s| = j} \ \prod_{i = 1}^j s_i \] 那么接下来，对于全部需要的 \(j\)，我们考虑从 \(F_{n}\) 转移到 \(F_{2n}\)：

一个很显然的想法，就是我们从 \([0, n - 1]\) 中选择 \(l\) 个，从 \([n, 2n - 1]\) 中选出剩下的，组成上面所提到的从集合 \([0, 2n-1]\) 中选出的大小为 \(j\) 子集；形式化地说就是将两部分的结果乘起来
前半部分的答案很显然是 \(F_{n, l}\)，而后半部分的答案我们没有维护；但是我们可以把它看作从 \([0, n - 1]\) 中选择了 \(j - l\) 个，然后对于每一个都加上了 \(n\)，也就是下面这样： \[ F'_{n, j'} = \sum_{s\subset [n, 2n-1] \and |s| = j'} \ \prod_{i = 0}^{j'}s_{i} = \sum_{s\subset [0, n-1] \and |s| = j'} \ \prod_{i = 0}^{j'}(s_{i} + n) \] 那么这个式子展开是什么样的呢？因为这个连乘长得非常像二项式展开~~但是不是，残念（~~，所以我们可以想象一下它展开后的样子： \[ F'_{n, j'} = \sum_{l = 0}^{j'} \mathbf{C}_{n - l}^{j'-l} \times n^{j'-l} \times \sum_{s\subset [0, n-1] \and |s| = l} \prod_{i = 0}^{l}s_i \] 上面的式子中，有 \(\mathbf{C}_{n - l}^{j' - l} = \mathbf{C}_n^{j'} \times \mathbf{C}_{j'}^l\)；首先是选出坐标的组合数，然后乘上“二项式系数”。
然后，观察上面的式子的后半部分，我们会惊喜地发现它就是 \(F_{n, l}\)，是我们已经维护的东西！

综上所述，我们可以通过下面的转移方程完成从 \(F_{n}\) 到 \(F_{2n}\) 的转移： \[ F_{2n, J} = \sum_{j = 0}^J F_{n, j} \times F'_{n, j'}, \ \ j + j' = J \] 上式中的 \(F'_{n, j}\) 可以通过 \(F_{n, j}\) 通过下面的多项式乘法转移得到： \[ F'_{n, j} = \sum_{l = 0}^j \mathbf{C}_{n - l}^{j - l} \times n^{j - l} \times F_{n, l} \] 当然，基础的从 \(F_{n - 1, j}\) 和 \(F_{n - 1, j - 1}\) 向 \(F_{n, j}\) 的转化仍然有效；因此我们可以转化到任何的 \(n\)：相当于我们从 \(n = 1\) 出发，然后使用 \(\times2\) 和 \(+1\) 操作构造任何的 \(n\) ——在构造的过程中完成上面的转移就可以了；一种很显然的思路就是二进制拆位，然后按位构造 \(n\)：

代码实现

基本的思路就是每次扩增 \(\times2\)，如果这一位为 1 就再额外进行一次 \(+1\) 扩增：

const int N = 500;
const int mod = 1e9 + 7;
longs inv[N], f[N], big[N], np[N], tmp[N];

void initInverse(int n, longs p) {
    inv[0] = inv[1] = 1;
    for(int i = 2; i <= n; i++)
        inv[i] = (p - p / i) * inv[p % i] % p;
    inv[0] = 0;
}

longs nCr(longs n, longs r) {
    longs ret = 1;
    for (auto i = n - r + 1; i <= n; ++ i)
        ret = ret * i % mod;
    for (int i = 1; i <= r; ++ i)
        ret = ret * inv[i] % mod;
    return ret;
}

void calculateBig(int k, longs n) {
    memset(big, 0, sizeof(longs) * (k + 1));
    memset(np, 0, sizeof(longs) * (k + 1));
    np[0] = 1;
    for (int i = 1; i <= k; ++ i)
        np[i] = n * np[i - 1] % mod;
    const auto lim = min((longs)k, n);
    for (int i = 0; i <= lim; ++ i)
        for (int j = 0; j <= i; ++ j) {
            auto t = nCr(n - j, i - j) * f[j] % mod * np[i - j] % mod;
            big[i] = (big[i] + t) % mod;
        }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(null), cout.tie(null);

    int n = $.nextInt(), k = $.nextInt();
    const bitset<32> binary = n;
    initInverse(N - 1, mod);
    longs now = f[0] = 1;
    for (int i = 30 - __builtin_clz(n); i >= 0; -- i) {
        calculateBig(k, now);
        memset(tmp, 0, sizeof(longs) * (k + 1));
        for (int s = 0; s <= k; ++ s)
            for (int b = 0; b <= k; ++ b)
                if (s + b <= k)
                    tmp[s + b] = (tmp[s + b] + f[s] * big[b]) % mod;
                else break;
        memcpy(f, tmp, sizeof(longs) * (k + 1));
        now *= 2;
        if (binary.test(i)) {
            memset(tmp, 0, sizeof(longs) * (k + 1));
            tmp[0] = 1;
            for (int j = 1; j <= k; ++ j)
                tmp[j] = (f[j] + now * f[j - 1]) % mod;
            memcpy(f, tmp, sizeof(longs) * (k + 1));
            ++ now;
        }
    }
    longs ans[] = {1, 0};
    vector<int> out;
    for (int j = 1; j <= k; ++ j) {
        ans[j % 2] = (ans[j % 2] + f[j]) % mod;
        out.push_back((int) ans[j % 2]);
    }
    $.putArray(out.begin(), out.end());

    return 0;
}

上面的代码中的 30 - __builtin_clz(n) 的含义是： int 类型的 n 的最高位的 1 的所在的位置的低一位的下标；我们使用它作为扩增起点——不使用最高位的原因是我们已经从 \(1\) 出发了，所以不需要对于首位的 \(1\) 进行额外的扩增。

当然，上面的实现中的每次转移的时间复杂度是 \(\mathcal{O}(k^2)\) 的，进行 \(\log_2n\) 次转移；如果可以使用各种手段加快单次转移的速度，理论上可以做到 \(k \leq 10^5\)（时间复杂度 \(\mathcal{O}(k\cdot \log k\log n)\)）~~但是我不会，原作者也不会~~

后记

罚时是真的多，，明明还是可以回到 1700 的场嗯给我打成了防掉分场，只能说非常地不行了（

最近的准度不行啊，还是以后要多加注意才行；补题也要进行的更加迅速才行，不然题目真的补不完力~~昨天半夜的 Div.1 + Div.2 还没有下落呜呜~~（呜呜呜

更新于：2021年4月24日

算法

ACM

Codeforces

在 Windows 10 设备上启动 FTP 服务

一些关于在 Windows 电脑上折腾 FTP 文件传输的记录。毕竟虽然但是，华科大内网的连接速度还是非常可以的，如果能够很好的借助 FTP 传输文件的话，倒也省得我带着移动硬盘在寝室和实验室来...

基础知识：错排问题

什么是错排问题？重排指的是在排列组合中，一个排列的所有的元素都不在原来的位置上；更加地形式化说明的话，就是对于一个包含 \(1\cdots n\) 全部 \(n\) 个元素的排列 \(p\)，按...

Codeforces Round#717 div.2 回顾

记录

题解

A - Tit for Tat

B - AGAGA XOOORRR

C - Baby Ehab Partitions Again

代码实现

D - Cut

代码实现

E - Baby Ehab Plays with Permutations

阳间做法

代码实现

阴间做法

代码实现

后记