标签: 矩阵

[洛谷4643]【模板】动态dp 题解

[洛谷4643]【模板】动态dp 题解

题目地址:洛谷:【P4643】【模板】动态dp – 洛谷 题目描述 给定一棵  …

[SDOI2009]HH去散步 题解

[SDOI2009]HH去散步 题解

题目地址:洛谷:【P2151】[SDOI2009]HH去散步 – 洛谷、BZO …

[洛谷1357]花园 题解

[洛谷1357]花园 题解

题目地址:洛谷:【P1357】花园 – 洛谷

题目描述

小L有一座环形花园,沿花园的顺时针方向,他把各个花圃编号为1~N(2<=N<=10^15)。他的环形花园每天都会换一个新花样,但他的花园都不外乎一个规则,任意相邻M(2<=M<=5,M<=N)个花圃中有不超过K(1<=K<M)个C形的花圃,其余花圃均为P形的花圃。
例如,N=10,M=5,K=3。则
CCPCPPPPCC 是一种不符合规则的花圃;
CCPPPPCPCP 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数Mod 1000000007

由于请您编写一个程序解决此题。

输入输出格式

输入格式:
一行,三个数N,M,K。

输出格式:
花园种数Mod 1000000007

输入输出样例

输入样例#1:

10 5 3

输出样例#1:

458

输入样例#2:

6 2 1

输出样例#2:

18

说明

【数据规模】
40%的数据中,N<=20;
60%的数据中,M=2;
80%的数据中,N<=10^5。
100%的数据中,N<=10^15。

题解

我们看一下M=2怎么做。我们枚举后面2个花圃的状态,一共有4种:CC、CP、PC、PP,设计状态dp[i][S]表示到第i个且末尾2个花圃的状态为S的方案数,然后枚举后面接上去哪个花圃来转移,如CC可以转移到CC和CP。如果M更大,到5了,就可以考虑状压这个状态来转移。转移同上,只是要把操作换为位运算。这样直接做的复杂度是[eq]O(n \cdot 2^{m})[/eq]的。
当n变得无法承受的时候,我们需要一个[eq]O(\log n)[/eq]的算法。这个时候我们想到了快速幂。我们知道,从一个状态向下一个状态的转移是一个固定不变的线性变换,既然如此,我们构建转移矩阵,进行矩阵快速幂计算转移矩阵的n次方即可。复杂度是[eq]O(\log n)[/eq]的(忽略矩阵乘法带来的开销)。
对于构造转移矩阵的方法,实际上矩阵的第i行表示下一层的i这个元素由这一层的元素乘上怎么样的系数加和得来的,因此对于[latex]i \rightarrow i'[/latex]这个转移,我们直接令[latex]trans_{i’, i} = 1[/latex]即可。由于初始的时候是一个单位矩阵,也可以不乘这个初始矩阵。
为什么不是n-m次幂?注意我们DP状态的定义,答案在dp[n][S]中,至于当i小于m的时候,实际上S多出来那部分的意义是在枚举这个序列末尾的情况,因为花园是个环嘛。答案计算的是[eq]\sum_S dp[n][S] = trans^n_{S, S}[/eq],是因为初始的时候是个列向量,是一排1,扩展成方阵以后就是单位矩阵了,最后肯定要按照列向量的意义计算,就取主对角线上的数值。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 50, MO = 1e9 + 7;

LL n, m, k, cnt[MAXN];

struct Matrix {
    LL a[MAXN][MAXN];
    Matrix() {
        memset(a, 0, sizeof(a));
    }
    inline Matrix operator*(const Matrix &rhs) const {
        Matrix res;
        for(int i = 0; i < 1 << m; i++) {
            for(int j = 0; j < 1 << m; j++) {
                for(int k = 0; k < 1 << m; k++) {
                    res.a[i][j] = (res.a[i][j] + a[i][k] * rhs.a[k][j] % MO) % MO;
                }
            }
        }
        return res;
    }
    inline Matrix& operator*=(const Matrix &x) {
        return *this = *this * x;
    }
};

inline Matrix fpow(Matrix mat, LL k) {
    Matrix res;
    for(int i = 0; i < 1 << m; i++) {
        res.a[i][i] = 1;
    }
    while(k) {
        if(k & 1) res *= mat;
        mat *= mat;
        k >>= 1;
    }
    return res;
}

int main() {
    n = readint(); m = readint(); k = readint();
    for(int i = 0; i < 1 << m; i++) {
        cnt[i] = cnt[i >> 1] + (i & 1);
    }
    Matrix trans;
    for(int i = 0; i < 1 << m; i++) {
        if(cnt[i] > k) continue;
        trans.a[i >> 1][i] = 1;
        trans.a[i >> 1 | (1 << (m - 1))][i] = 1;
    }
    trans = fpow(trans, n);
    LL res = 0;
    for(int i = 0; i < 1 << m; i++) {
        res = (res + trans.a[i][i]) % MO;
    }
    printf("%lld", res);
    return 0;
}
[HNOI2008]GT考试 题解

[HNOI2008]GT考试 题解

题目地址:洛谷:【P3193】[HNOI2008]GT考试 – 洛谷、BZOJ …

高斯-约旦消元法原理及实现

高斯-约旦消元法原理及实现

概述 高斯-约旦消元是一种方便计算线性方程组的方法。下面我们介绍它的原理及实现。 原理 思 …

数学笔记:矩阵、行列式

数学笔记:矩阵、行列式

矩阵(Matrix)

一个[latex]m \times n[/latex]的矩阵是一个由[latex]m[/latex]行[latex]n[/latex]列元素排列成的矩形阵列。元素可以是数字、符号或数学式。

矩阵的基本运算

加(减)法

[latex]m \times n[/latex]矩阵[latex]\mathbf{A}[/latex]和[latex]\mathbf{B}[/latex]的和(差):[latex]\mathbf{A} \pm \mathbf{B}[/latex]为一个[latex]m \times n[/latex]矩阵,其中每个元素是A和B相应元素的和(差),也就是说[latex] (\mathbf{A} \pm \mathbf{B})_{i, j} = \mathbf{A}_{i, j} \pm \mathbf{B}_{i, j} [/latex]。

数乘

标量[latex]c[/latex]与矩阵[latex]\mathbf{A}[/latex]的数乘:[latex]c\mathbf{A}[/latex]的每个元素是A的相应元素与c的乘积,也就是说[latex] (c\mathbf{A})_{i, j} = c \cdot \mathbf{A}_{i, j} [/latex]。

转置

[latex]m \times n[/latex]矩阵[latex]\mathbf{A}[/latex]的转置是一个[latex]n \times m[/latex]的矩阵,记为[latex]\mathbf{A}^T[/latex],其中的第[latex]i[/latex]个行矢量是原矩阵[latex]\mathbf{A}[/latex]的第[latex]i[/latex]个列矢量;或者说,[latex] (\mathbf{A}^T)_{i, j} = \mathbf{A}_{j, i} [/latex]。

运算律

矩阵的加法运算满足交换律:[latex]\mathbf{A} + \mathbf{B} = \mathbf{B} + \mathbf{A}[/latex]
矩阵的转置和数乘运算对加法满足分配率:[latex] (\mathbf{A} + \mathbf{B})^T = \mathbf{A}^T + \mathbf{B}^T [/latex];[latex] c(\mathbf{A} + \mathbf{B}) = c\mathbf{A} + c\mathbf{B} [/latex]
转置和数乘运算满足类似于结合律的规律:[latex] c(\mathbf{A}^T) = (c\mathbf{A}^T) [/latex]

矩阵乘法

两个矩阵的乘法仅当第一个矩阵[latex]\mathbf{A}[/latex]的列数和另一个矩阵[latex]\mathbf{B}[/latex]的行数相等时才能定义。如[latex]\mathbf{A}[/latex]是[latex]m \times n[/latex]矩阵和[latex]\mathbf{B}[/latex]是[latex]n \times p[/latex]矩阵,它们的乘积[latex]\mathbf{AB}[/latex]是一个[latex]m \times p[/latex]矩阵,且
[latex display=”true”] (\mathbf{AB})_{i, j} = \sum_{r=1}^n \mathbf{A}_{i, r} \mathbf{B}_{r, j} [/latex]
运算律:
– 结合律:[latex] (\mathbf{AB})\mathbf{C} = \mathbf{A}(\mathbf{BC}) [/latex]
– 左分配律:[latex] (\mathbf{A} + \mathbf{B})\mathbf{C} = \mathbf{AC} + \mathbf{BC} [/latex]
– 右分配律:[latex] \mathbf{C}(\mathbf{A} + \mathbf{B}) = \mathbf{CA} + \mathbf{CB} [/latex]
– [latex] c(\mathbf{AB}) = (c\mathbf{A})\mathbf{B} = \mathbf{A}(c\mathbf{B}) [/latex]
– [latex] (\mathbf{AB})^T = \mathbf{B}^T\mathbf{A}^T [/latex]
– 不满足交换律。[latex]\mathbf{AB}[/latex]存在,[latex]\mathbf{BA}[/latex]不一定存在。即使存在,也可能[latex]\mathbf{AB} \neq \mathbf{BA}[/latex]。

单位矩阵(Identity matrix)

[latex]n[/latex]阶单位矩阵,是一个[latex]n \times n[/latex]的方形矩阵,其主对角线元素为1,其余元素为0,记作[latex]\mathbf{I}_n[/latex]或者[latex]\mathbf{E}_n[/latex],阶数可以省略。
[latex display=”true”]\begin{aligned} \mathbf{I}_1 &= \begin{bmatrix} 1 \end{bmatrix} \\ \mathbf{I}_2 &= \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \\ \mathbf{I}_3 &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \\ \cdots \\ \mathbf{I}_n &= \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix} \end{aligned}[/latex]

行列式(Determinant)

记法:矩阵[latex]\mathbf{A}[/latex]的行列式可以记作[latex]|\mathbf{A}|[/latex]或[latex]\mathrm{det}(\mathbf{A})[/latex]。也可以直观地把矩阵的方括号换成垂直线表示。
直观定义:参见行列式 – 维基百科,自由的百科全书。
2阶矩阵的行列式:[latex]\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad – bc[/latex]
3阶矩阵的行列式:主对角线乘积之和减副对角线元素乘积之和
几何意义:行向量/列向量张成的体积/面积。
更多内容参见行列式 – 维基百科,自由的百科全书。

范德蒙矩阵(Vandermonde matrix)

范德蒙矩阵是一个各列呈现出几何级数关系的矩阵,例如
[latex display=”true”]\mathbf{V} = \begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \cdots & \alpha_1^{n-1} \\ 1 & \alpha_2 & \alpha_2^2 & \cdots & \alpha_2^{n-1} \\ 1 & \alpha_3 & \alpha_3^2 & \cdots & \alpha_3^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_m & \alpha_m^2 & \cdots & \alpha_m^{n-1} \end{bmatrix}[/latex]
或者表达为[latex]\mathbf{V}_{i, j} = \alpha_i^{j-1}[/latex]。
[latex]n[/latex]阶范德蒙矩阵的行列式可以表示为:
[latex display=”true”]\mathrm{det}(\mathbf{V}) = \prod_{1 \leq i < j \leq n}(\alpha_j – \alpha_i)[/latex]
当[latex]\alpha_i[/latex]各不相同时,[latex]\mathrm{det}(\mathbf{V})[/latex]不为零。

参考资料

[POJ3734]Blocks 题解

[POJ3734]Blocks 题解

题目地址:POJ:3734 — Blocks 题目描述 Panda has r …