Codeforces Round 940 (Div. 2)

这场还挺Edu的

C. How Does the Rook Move?

Problem - C - Codeforces

  • 数学方法

​ 我用的数学方法，卡了很久才推出来思路和式子。

​ 首先行列其实等价，直接单考虑剩余 (n) 行就行。

​ 这类题应该选择先选一个东西，然后处理剩下的东西。

​ 这里好做的方法是先选 (m) 个 ((r, c)(r = c)) 的格子，每次会耗费一个格子，后选 (n - m) ((r,c)(r\neq c))的格子，每次会耗费两个格子。

​ 因为后选的格子每次会耗费两个，所以要保证留给后选的数目必须为偶数。

​ 所以大体流程就是枚举所有的 (m(m < n, (n - m)\mid 2))，然后推式子：

​ 这里推选 (m) 个的比较直接：(\binom{n}{m})。

​ 但是剩下的那个卡了我半小时：

​ 我们还剩下 (n - m) 行/列，而且必须是偶数（第2类棋不能走完奇数行/列）。

​ 我们可以看到，剩余列的 ((n - m)!) 每一种排列都对应着一组我们可以下的棋步。例如，如果我们还剩下 ((1, 4, 5, 6)) 列，那么 ((4, 5, 6, 1)) 排列对应于下 ((4, 5), (6, 1)) 步棋。然而，如果我们只是简单地计算排列数，那么我们也将计算排列 ((6, 1, 4, 5)) ，它对应的是同一组棋步。

​ 为了消除多算，我们可以用 ((n - m)!) 除以 (((n - m)/2)!) （去除所选棋子对的排列）。

​ 因此，答案变为

​ (\sum\limits_{c = 0}^m [(n - m) \bmod 2 = 0] {n \choose m} \frac{(n - m)!}{\left(\frac{n - m}{2}\right)!})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
#define tests
    int n, k;
    std::cin >> n >> k;
    std::vector<bool> vis(n);
    for (int i = 0, r, c; i < k; i++) {
        std::cin >> r >> c;
        --r, --c;
        vis[r] = vis[c] = true;
    }
    int cntNotVis(std::count(all(vis), false));
    Z ans {};
    for (int m = cntNotVis & 1; m <= cntNotVis; m += 2) {
        ans += comb.binom(cntNotVis, m) * comb.fac(cntNotVis - m) / comb.fac((cntNotVis - m) / 2);
    }
    std::cout << ans << '\n';
}
  • 动态规划

​ 赛时也有往这个方向考虑，但是不知道怎么转移。

​ 移动基本上有两种类型：

  1. 在某个 ((i, i)) 位置放置车：这将减少 (1) 的空闲行列数。
  2. 将车置于 ((i, j)) ，其中 (i \neq j) ：现在计算机也会这样做，将车置于 ((j, i)) 处，挡住 (i) 和 (j) 行以及 (i) 和 (j) 列。因此空闲行列数减少了 (2) 。

​ 首先，我们算出之前下过的 (k) 步，并计算剩余可放置车的空闲列/行的数量，称之为 (m) 。

​ 注意移行/列的顺序并不影响车的最终配置，因此只有行数才是决定最终配置数的关键。

​ 定义 (dp[i]) 表示当剩下 (i) 行和列时的最终配置数。

​ 由于移除行/列的顺序并不重要，我们从移除最后一行或最后一列开始。

​ 在移除 (i \times i) 网格中的最后一行或最后一列时，我们有两种选择：

  • 我们放置车 ((i, i)) ，结果是只删除最后一行和一列，留下一个 ((i-1) \times (i-1)) 格。这种情况下的最终配置数为 (dp[i-1]) 。
  • 或者，我们也可以在 ((i, j)) 或 ((j, i)) 中的任意 (j \in {1, 2, \ldots, i-1}) 放置车。这步棋之后， (j) th和 (i) th行列都被删除，剩下一个 ((i-2) \times (i-2)) 格。这就为 (dp[i]) 贡献了 (2 (i-1) \cdot dp[i-2]) 。

总的来说，我们计算了所有 (i \in {2, 3, \ldots, n}) 的 (dp[i] = dp[i-1] + 2 (i-1) \cdot dp[i-2]) ，基本情况为 (dp[0] = dp[1] = 1) 。

我们的最终答案是 (dp[m]) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (t--) {
    int n, k;
    cin >> n >> k;
    int used = 0;
    for (int i = 0; i < k; i++) {
        int r, c;
        cin >> r >> c;
        used += 2 - (r == c);
    }
    int m = n - used;
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= m; i++)
        dp[i] = (dp[i - 1] + 2ll * (i - 1) * dp[i - 2] % MOD) % MOD;
    cout << dp[m] << "\n";
}

D. A BIT of an Inequality

Problem - D - Codeforces

二进制拆位前缀和，只是维护的是到当前这位的 (1) 的个数为奇数的个数。

维护出来之后对每个 (y) 找最高位的 (1)，显然 (f(x,z)) 和 (f(y,z)) 的这一位的 (1) 的个数之和只要为偶数，那么 (f(x, y)\oplus f(y, z) > f(x, z)) 因为此时 (f(x, z)) 这一位为 (0) 了，而 (f(x, y)\oplus f(y,z)) 这一位仍为 (1)。

显然为偶数的情况要么是奇数加奇数，要么是偶数加偶数。

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
void solve()
{
#define tests
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a)
        std::cin >> x;
    std::vector dp(31, std::vector<int>(n + 1)); // 拆位前缀和
    for (int i = 0; i < 31; i++) {
        int sum {};
        for (int j = 0; j < n; j++) {
            sum = (sum + (a[j] >> i & 1)) & 1; // 统计1的个数是不是奇数
            if (sum == 1) {
                dp[i][j + 1] = dp[i][j] + 1;
            } else {
                dp[i][j + 1] = dp[i][j];
            }
        }
    }
    i64 res {};
    for (int i = 0; i < n; i++) {
        int p {};
        for (int j = 30; j >= 0; j--) { // 找这个数最大为1的位
            if (a[i] >> j & 1) {
                p = j;
                break;
            }
        }
        // 奇数 + 奇数的方案
        i64 add1(1LL * dp[p][i] * (dp[p][n] - dp[p][i]));
        i64 add2(1LL * (i + 1 - dp[p][i]) * (n - i - (dp[p][n] - dp[p][i])));
        // 偶数 + 偶数的方案

        res += add1 + add2;
    }
    std::cout << res << '\n';
}