动态规划

普通矩阵快速幂

// ============================================================
// 普通矩阵 + 矩阵快速幂模板（模 MOD）
// ============================================================
// 当前支持：
//   1. 任意行列矩阵
//   2. 矩阵加法、减法、乘法
//   3. 单位矩阵 Matrix::identity(n)
//   4. 方阵快速幂 qpow(base, exp)
//   5. 矩阵乘列向量 multiply_vector(v)
//
// 默认语义：
//   普通模意义矩阵乘法：
//     C[i][j] = sum(A[i][k] * B[k][j]) % MOD
//   下标从 0 开始。
//
// 换题时常见改动：
//   1. 固定小矩阵且特别卡常：把 vector 改成静态数组 int a[N][N]。
//   2. 不取模：删除 norm() 和所有 % MOD，但要检查是否会溢出。
//   3. MOD 不是全局常量：可以给 Matrix 增加成员 mod，并保证参与运算的矩阵 mod 相同。
//   4. max-plus / min-plus：不能只把 MOD 删除。
//      max-plus 要把“加法”改为 max，把“乘法”改为 +，
//      单位矩阵对角线为 0，其余位置为负无穷。
//      当前目录已有“矩阵快速幂 max-plus.cpp”作为对应示例。
//   5. 行向量转移通常写 old_dp * trans；列向量转移通常写 trans * old_dp。
//      建转移矩阵前一定先确定自己采用哪种方向。
//
// 注意：
//   - qpow 只接受方阵。
//   - 默认依赖外部的 constexpr int MOD。
//   - 在 #define int long long 的代码风格下，两个模数内元素相乘通常可放入 long long；
//     如果 MOD 更大，乘法应改用 __int128。
// ============================================================
 
class Matrix
{
private:
    int row, col;
    vector<vector<int>> a;
 
    int norm(int x) const
    {
        x %= MOD;
        if (x < 0)
        {
            x += MOD;
        }
        return x;
    }
 
public:
    Matrix(int row = 0, int col = 0, int val = 0)
        : row(row), col(col), a(row, vector<int>(col, norm(val)))
    {
    }
 
    Matrix(const vector<vector<int>> &v)
        : row(v.size()), col(v.empty() ? 0 : v[0].size()), a(v)
    {
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                a[i][j] = norm(a[i][j]);
            }
        }
    }
 
    static Matrix identity(int n)
    {
        Matrix ans(n, n);
        for (int i = 0; i < n; i++)
        {
            ans[i][i] = 1;
        }
        return ans;
    }
 
    vector<int> &operator[](int i)
    {
        return a[i];
    }
 
    const vector<int> &operator[](int i) const
    {
        return a[i];
    }
 
    int rows() const
    {
        return row;
    }
 
    int cols() const
    {
        return col;
    }
 
    Matrix operator+(const Matrix &other) const
    {
        Matrix ans(row, col);
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                ans[i][j] = norm(a[i][j] + other[i][j]);
            }
        }
        return ans;
    }
 
    Matrix operator-(const Matrix &other) const
    {
        Matrix ans(row, col);
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                ans[i][j] = norm(a[i][j] - other[i][j]);
            }
        }
        return ans;
    }
 
    Matrix operator*(const Matrix &other) const
    {
        Matrix ans(row, other.col);
        for (int i = 0; i < row; i++)
        {
            for (int k = 0; k < col; k++)
            {
                if (a[i][k] == 0)
                {
                    continue;
                }
                for (int j = 0; j < other.col; j++)
                {
                    ans[i][j] = (ans[i][j] + a[i][k] * other[k][j]) % MOD;
                }
            }
        }
        return ans;
    }
 
    Matrix &operator+=(const Matrix &other)
    {
        return *this = *this + other;
    }
 
    Matrix &operator-=(const Matrix &other)
    {
        return *this = *this - other;
    }
 
    Matrix &operator*=(const Matrix &other)
    {
        return *this = *this * other;
    }
 
    vector<int> multiply_vector(const vector<int> &v) const
    {
        vector<int> ans(row);
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                ans[i] = (ans[i] + a[i][j] * norm(v[j])) % MOD;
            }
        }
        return ans;
    }
};
 
Matrix qpow(Matrix base, int exp)
{
    Matrix ans = Matrix::identity(base.rows());
    while (exp)
    {
        if (exp & 1)
        {
            ans *= base;
        }
        base *= base;
        exp >>= 1;
    }
    return ans;
}

0/1 与完全背包

// 0/1 背包：每件物品最多一次，容量不超过 W。
vector<long long> zero_one_knapsack(
    int W, const vector<pair<int, int>>& items) {
    vector<long long> dp(W + 1);
    for (auto [weight, value] : items)
        for (int j = W; j >= weight; --j)
            dp[j] = max(dp[j], dp[j - weight] + value);
    return dp;
}
 
// 完全背包：每件物品可用任意次。
vector<long long> complete_knapsack(
    int W, const vector<pair<int, int>>& items) {
    vector<long long> dp(W + 1);
    for (auto [weight, value] : items)
        for (int j = weight; j <= W; ++j)
            dp[j] = max(dp[j], dp[j - weight] + value);
    return dp;
}