2025年2月写的一些codeforces题

[[ slider_text ]]

[[ item.c ]]

2025年2月写的一些codeforces题

发布时间 2025-02-15 作者：zhangminchen 来源：算法小站

区间dp 矩阵运算 高斯消元

## Codeforces Round 979 (Div. 2)
### D
**[D. QED's Favorite Permutation](https://codeforces.com/contest/2030/problem/D)**
给你一个排列，一个操作序列`s`包含`L, R`，现在有若干个询问，每个询问给一个数$$i$$
下面问，操作序列`s[i]`位置从`L <-> R`（取反），并且这样的修改是永久的
询问之前，排列都会回到初始状态（询问是独立的），问能不能根据操作序列，将序列变成非递减
注意，`s[i] = R`，说明可以`s[i] <-> s[i+1]`，`s[i] = L`对称

**算法分析**
![](/media/content_img/CF979D1.png)
![](/media/content_img/CF979D2.png)

**存在的一些错误思路**
![](/media/content_img/CF979D3.png)

## Codeforces Round 1004 (Div. 2)
### F
**[F. Bitwise Slides](https://codeforces.com/contest/2067/problem/F)**
给你一个数组`a`，同时给你三个变量`P, Q, R`一开始都是`0`
必须按照$$1\sim n$$的顺序，按顺序处理所有的数字$$a_1 \cdots a_n$$，在处理$$a_i$$的时候
执行三种操作之一

```math
P = P \oplus a_i \\
Q = Q \oplus a_i \\
R = R \oplus a_i
```
给定一个规则，就是$$P, Q,R$$不能**三个都不同（至少要存在一个二元组，使二元组中的数相等）**
符合规则的情况是
```bash
PPP, QQQ, RRR

PPQ, PPR
QQP, QQR
RRP,  RRQ

(相同字符表示相同的数)

（P, Q, R是不可以的）
```
一共有$$3^n$$种方法来处理这些数，问最后有多少种处理方案，使得最后的结果符合上述规则
三个数，**至少要有一对数是相同的**，问这样的方案数

```bash
样例
a = [1 7 9]，操作序列 RRR

R = 1 ^ 7 ^ 9 = 15
P = 0
Q = 0

(15, 0, 0) 是一个合法的解，因为`(0, 0)`相同

另外注意，其他操作序列都不可以
比如 RRP
那么会出现 R = 1^7 = 6,  P = 9, Q = 0
(6, 9, 0)两两不同，不合法
```

**算法分析**
![](/media/content_img/CF1004F1.png)
![](/media/content_img/CF1004F2.png)

**算法实现优化**
不难发现，`last -> dp` 转移中，只有关于 `dp[sum]` 的状态会变化
其他都是**原封不动**的

```bash
	map<int, mint> dp, last;
	dp[0] = 1
	
    for (int i = 1; i <= n; i++) {
        last = dp, dp.clear();
        auto sum = pre[i-1];

for (auto [x, dpv] : last) {
            if (sum == x) dp[sum] += 3 * last[sum];
            else {
                dp[x] += last[x];

if ((x ^ a[i]) == sum)
                    dp[sum] += 2 * last[sum ^ a[i]];
            }
        }
    }
	
优化思路如下
注意到 last = dp, dp.clear() 之后
else 执行了 dp[x] += last[x]

这说明了什么？说明了这是从 last -> dp 原封不动的状态转移，所以没有必要遍历所有 last 中的状态
因为 last -> dp，dp 所有状态都是从 last 中继承过来的

只需要看在上面的情况中，dp 相对于 last，增加了（减少了）多少，去维护这个变化量即可

比如做这样的拆分
if (sum == x) {
	dp[sum] += 2 * last[sum];
	dp[x] += last[x];
}

不难发现，last -> dp 转移中，只有关于 dp[sum] 的状态会变化
其他都是原封不动的
```

算法优化如下
```bash
    map<int, mint> dp, last;
    dp[0] = 1;

for (int i = 1; i <= n; i++) {
        auto sum = pre[i-1];
        // x = sum
        mint add = 0;
        if (dp.contains(sum)) {
            add += 2 * dp[sum];
        }
        if (dp.contains(sum ^ a[i])) {
            add += 2 * dp[sum ^ a[i]];
        }
        dp[sum] += add;
    }
```

**一般转移优化的思路如下**
有时候对于更复杂的问题，类似的，大多数状态，都是原封不动的`dp[x] <-- last[x]`
只有很少的状态会发生变化，我们把**所有可能发生变化**的二元组`(x, add)`缓存到`chg 容器`中
其中`x`表示`dp(x)`这个状态可能会发生变化，`add`表示变化的增量，这样
```bash
for (auto [x, add] : chg) {
	dp[x] += add
}
```
比如这个问题，优化代码也可以这样写
```bash
for (int i = 1; i <= n; i++) {
	auto sum = pre[i-1];
	// x = sum
	vector<pair<int, mint> > chg;
	if (dp.contains(sum)) {
		auto x = sum;
		chg.emplace_back(sum, 2 * dp[x]);
	}
	if (dp.contains(sum ^ a[i])) {
		auto x = sum ^ a[i];
		chg.emplace_back(sum, 2 * dp[x]);
	}
	for (auto [x, add] : chg) dp[x] += add;
}
```

## 高斯消元
### 高斯消元求矩阵的秩
![](/media/content_img/gauss01.png)

### 高斯消元求线性方程组的解
先进行普通的高斯消元
![](/media/content_img/gauss02.png)

接着考虑化为仅$$a(i, i) = 1$$，其他位置都是`0`的矩阵，求出线性方程组的解
![](/media/content_img/gauss03.png)

### 高斯消元求矩阵的逆
![](/media/content_img/gauss04.png)

### 矩阵类的实现
```bash
template<typename T>
class Matrix {
public:
    vector<vector<T> > data;

// 下标都是从 0 开始
    explicit Matrix(int n = 0, int m = 0) {
        data = vector<vector<T> > (n, vector<T>(m, 0));
    }
    explicit Matrix(const vector<vector<T> > &_v) : data(_v) {}

pair<int, int> size() const {
        if (data.size()) return {data.size(), data.back().size()};
        return {0, 0};
    }

int rank() const {
        auto [n, m] = size();
        vector<vector<T> > a = (n <= m ? this->data : transpose().data);
        if (n > m) swap(n, m);

int i, j, k, l, r = 0;
        for (i = 0, j = 0; i < n && j < m; j++) {
            for (k = i; k < n; k++) if (a[k][j]) break;

if (k == n) continue;
            swap(a[i], a[k]);

// a[i] -> e
            auto pivot = a[i][j];
            // i64 iv = power(a[i][j], P - 2);
            for (k = j; k < m; k++) a[i][k] = a[i][k] / pivot;
            // for (k = j; k < m; k++) a[i][k] = a[i][k] * iv % P;

// use a[i] eliminate a[i+1], a[i+2], ..., a[n-1]
            for (k = i+1; k < n; k++) for (int l = j+1; l < m; l++) {
                a[k][l] = a[k][l] - a[k][j] * a[i][l];
                // a[k][l] = ( a[k][l] + (P - a[k][j]) * a[i][l] ) % P;
            }
            ++i, ++r;
        }

return r;
    }

friend constexpr std::istream &operator>> (std::istream &is, Matrix &r) {
        for (auto &v : r.data) for (auto &x : v) {
            is >> x;
        }
        return is;
    }

friend constexpr std::ostream &operator<< (std::ostream &os, const Matrix &r) {
        const auto [n, m] = r.size();
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            os << r.data[i][j] << " \n"[j + 1 == m];
        }
        return os;
    }
    constexpr Matrix &operator+= (const Matrix &b) {
        assert(data.size() == b.data.size());
        auto [n, m] = this->size();

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            data[i][j] += b.data[i][j];
        }
        return *this;
    }

constexpr Matrix &operator-= (const Matrix &b) {
        assert(data.size() == b.data.size());
        auto [n, m] = this->size();

for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            data[i][j] -= b.data[i][j];
        }

return *this;
    }

constexpr Matrix operator* (const Matrix &b) const {
        auto [n, m] = size();
        auto [_, q] = b.size();
        assert(m == _);

Matrix res(n, q);
        for (int k = 0; k < m; k++) {
            for (int i = 0; i < n; i++) for (int j = 0; j < q; j++) {
                res.data[i][j] += data[i][k] * b.data[k][j];
            }

// 特别注意，矩阵数据类型是 u64，才可以这样用
            // 否则，Matrix<mint>，用常规取模
            if (!( (k ^ (q-1)) & 15 )) for (auto &v : res.data) for (u64 &x : v) x %= this->P;
        }
        return res;
    }
    constexpr Matrix &operator*= (const Matrix &b) {
        return *this = *this * b;
    }

friend constexpr Matrix operator+ (Matrix lhs, const Matrix &rhs) {
        lhs += rhs;
        return lhs;
    }

friend constexpr Matrix operator- (Matrix lhs, const Matrix &rhs) {
        lhs -= rhs;
        return lhs;
    }

Matrix transpose() const {
        auto [n, m] = this->size();
        Matrix res(m, n);
        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
            res.data[j][i] = this->data[i][j];
        }
        return res;
    }

// Ax = b
    vector<T> gauss(vector<T> b) {
        auto [n, m] = this->size();
        if (b.size() != n) return {};

auto a = this->data;

for (int i = 0; i < n; i++) {
            int k;
            for (k = i; k < n; k++) {
                if (a[k][i] != 0) break;
            }
            swap(a[i], a[k]), swap(b[i], b[k]);

// a[i] -> e
            auto pivot = a[i][i];
            for (int j = i; j < n; j++) a[i][j] = a[i][j] / pivot;
            b[i] = b[i] / pivot;

// use a[i] to eliminate a[0...n-1]
            for (int j = 0; j < n; j++) {
                if (j == i) continue;

auto x = a[j][i];
                for (int k = i; k < n; k++) {
                    a[j][k] = a[j][k] - x * a[i][k];
                }

b[j] = b[j] - x * b[i];
            }
        }
        return b;
    }

Matrix<T> inverse() const {
        auto [n, m] = this->size();
        auto a = this->data;

for (int i = 0; i < n; i++) {
            int k;
            for (k = i; k < n; k++) {
                if (a[k][i] != 0) break;
            }
            if (k >= n) return Matrix({});
            swap(a[i], a[k]);
    
            // a[i] -> e
            auto pivot = a[i][i];
            for (int j = i; j < m; j++) a[i][j] = a[i][j] / pivot;

// use a[i] to eliminate a[0...n-1]
            for (int j = 0; j < n; j++) {
                if (j == i) continue;
    
                auto x = a[j][i];
                for (int k = i+1; k < m; k++) {
                    a[j][k] = a[j][k] - x * a[i][k];
                }
            }
        }
        //debug(a);

vector<vector<T> > res;
        for (auto v : a) {
            // debug(v);
            if (v.empty()) return Matrix({});
            res.emplace_back(v.begin()+n, v.end());
        }
        // // debug(res);
        return Matrix(res);
    }

// E
    Matrix E(int n) {
        Matrix r(n, n);
        for (int i = 0; i < n; i++) {
            r.data[i][i] = 1;
        }

return r;
    }

// power
    Matrix power(i64 k) {
        assert(k >= 0);
        auto a = *this;
        auto [n, m] = this->size();

assert(n == m);
        Matrix res = (k & 1 ? a : E(n));
        k >>= 1;

while (k) {
            a *= a;
            if (k & 1) res *= a;
            k >>= 1;
        }
        return res;
    }

private:
    static int P;
};

template<typename T>
int Matrix<T>::P = 1e9 + 7;
```

## 牛客小白月赛110
**[E.智乃的跳跃排序](https://ac.nowcoder.com/acm/contest/101918/E)**
给你一个序列，每个数都不同，有限制
每次只能交换下标$$|i-j| = k$$，或者是值$$|a_i - a_j| = k$$的$$i, j$$两个位置上的值
问能不能将其排序？

**算法分析**
![](/media/content_img/nowcoder110E1.png)
![](/media/content_img/nowcoder110E2.png)
![](/media/content_img/nowcoder110E3.png)

**[D.智乃与长短期主义者博弈](https://ac.nowcoder.com/acm/contest/101918/D)**
两个人轮流取数，短期主义只取两端最大的，长期主义者会根据短期主义者的决策，来取数，以获得全局最优
问最后两人的分数

**算法分析**
序列两端取数，并且**一个人能取什么数，是基于上一个人的状态**，这是典型的**区间 dp**
实际上，**连续的一段数，每次决策必须基于上一次的状态**，这样的问题都可以考虑区间 dp

状态设计如下
1.$$dp(i, j, 0)$$表示短期主义者在区间$$[i, j]$$能够选到的和（这部分转移是确定的）
2.$$dp(i, j, 1)$$表示长期主义者，在$$[i, j]$$能够选到的**最大的和**，这部分转移需要考虑最优解

然后根据还剩下的数的奇偶性，来看一下当前是谁先手，来写状态转移方程
```bash
初始化
(1) n 为奇数，取到最后一个数的一定是短期主义者
dp(i, i, 0) = a[i]
dp(i, i, 1) = 0

(2) n 位偶数，对称地，类似

转移，区间 dp，take = n - len
(1) take 为偶数
取 i 还是取 j，按题目要求来，假设是取 i
dp(i, j, 0) <-- dp(i+1, j, 0) + a[i]
dp(i, j, 1) <-- dp(i+1, j, 1)

(2) take 为奇数
costi = dp(i+1, j, 1) + a[i]
costj = dp(i, j-1, 1) + a[j]

如果 costi > costj，dp(i, j, 0) <-- dp(i+1, j, 0)
否则 dp(i, j, 0) <-- dp(i, j-1, 0)

dp(i, j, 1) = max(costi, costj)
```

上一篇：2025年一月算法比赛（二）下一篇：2025年2月写的一些codeforces题（二）

看完文章有啥想法