Codeforces Round#717 div.2 回顾

记录

比赛的那天 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 这种代码呢？以为很对称🐎（

B - AGAGA XOOORRR

考虑到最后只可能剩下两个相同的元素或三个相同的元素——因为更多的元素都可以合并到这两种情况上，所以只需要分别处理即可：

const int N = 2060;
uint a[N], sum[N];

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

    int T = $.nextInt(), n;
    while (T --) {
        $(n).nextArray(a + 1, a + 1 + n);
        for (int i = 1; i <= n; ++ i)
            sum[i] = sum[i - 1] ^ a[i];
        bool found = false;
        for (int i = 1; i <= n; ++ i)
            if (sum[i] == (sum[n] ^ sum[i]))
                found = true;
        for (int i = 1; i <= n; ++ i)
            for (int j = i; j <= n; ++ j)
                if (sum[i] == (sum[j] ^ sum[i]) &&
                    sum[i] == (sum[n] ^ sum[j]))
                found = true;
        $.put(found ? "YES" : "NO");
    }

    return 0;
}

之前白给成了直接排除一个元素，显然这是不科学的（

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 - 1}$ 向 $F_n$ $F_{n}$ 转移；即每次将 $n$ $n$ 放入长度为 $n - 1$ $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)$ ）~~但是我不会，原作者也不会~~