月度归档: 2018 年 3 月

[洛谷1919]【模板】A*B Problem升级版(FFT快速傅里叶) 题解

[洛谷1919]【模板】A*B Problem升级版(FFT快速傅里叶) 题解

题目地址:洛谷:【P1919】【模板】A*B Problem升级版(FFT快速傅里叶) & 

快速傅里叶变换(FFT)原理与实现

快速傅里叶变换(FFT)原理与实现

这篇文章写得很烂,而且大部分来自于算导,如有感兴趣者可以直接阅读算导或参考资料QAQ!本文 

数学笔记:矩阵、行列式

数学笔记:矩阵、行列式

矩阵(Matrix)

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

矩阵的基本运算

加(减)法

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

数乘

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

转置

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

运算律

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

矩阵乘法

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

单位矩阵(Identity matrix)

n阶单位矩阵,是一个n \times n的方形矩阵,其主对角线元素为1,其余元素为0,记作\mathbf{I}_n或者\mathbf{E}_n,阶数可以省略。
\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}

行列式(Determinant)

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

范德蒙矩阵(Vandermonde matrix)

范德蒙矩阵是一个各列呈现出几何级数关系的矩阵,例如
\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}
或者表达为\mathbf{V}_{i, j} = \alpha_i^{j-1}
n阶范德蒙矩阵的行列式可以表示为:
\mathrm{det}(\mathbf{V}) = \prod_{1 \leq i < j \leq n}(\alpha_j - \alpha_i)
\alpha_i各不相同时,\mathrm{det}(\mathbf{V})不为零。

参考资料

数学笔记:复数

数学笔记:复数

虚数单位(Imaginary unit) 虚数单位定义为二次方程式的两个解答中的一个解答。 

[CF364D]Ghd 题解

[CF364D]Ghd 题解

题目地址:Codeforces:Problem – 364D –  

[WF2015]Cutting Cheese 题解

[WF2015]Cutting Cheese 题解

题目地址:UVa:UVa Online Judge、洛谷:【UVA1712】Cutting Cheese – 洛谷

题目描述

原题面参见UVa/vjudge。
给你一个100*100*100的大方块,里面有若干球形空缺,要求切成s个体积相同的小方块,求每一块的厚度。

题解

简单的计算几何。
我们考虑球形体积和球缺体积的算法
\begin{aligned} V_{\text{ball}} &= \frac{4}{3} \pi r^3 \\ V_{\text{cap}} &= \pi h^2 (r - \frac{h}{3}) \end{aligned}
对于每一块,我们二分计算它与之前所有块加起来的厚度(因为这样只需要考虑切面的球缺),每次计算块体积的时候遍历球体,如果完全包含减体积,如果部分包含减球缺体积,

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cmath>

typedef long double LD;

const int MAXN = 10005;
const LD PI = acos(-1), EPS = 1e-12;

inline LD getballv(LD r) {
    return r * r * r * 4 / 3 * PI;
}

inline LD getballvq(LD r, LD h) {
    return PI * (3 * r - h) * h * h / 3;
}

int n, s;
LD z[MAXN], r[MAXN], len[MAXN], v;

inline LD getblockv(LD l) {
    LD res = l * 100 * 100;
    for(int i = 1; i <= n; i++) {
        if(z[i] + r[i] <= l) {
            res -= getballv(r[i]);
        } else if(z[i] - r[i] < l) {
            res -= getballvq(r[i], r[i] - z[i] + l);
        }
    }
    return res;
}

inline LD cal(LD v) {
    LD l = 0, r = 100, mid;
    while(r - l > EPS) {
        mid = (l + r) / 2;
        if(getblockv(mid) <= v) l = mid; else r = mid;
    }
    return l;
}

int main() {
    while(scanf("%d%d", &n, &s) != EOF) {
        v = 100 * 100 * 100;
        for(int i = 1; i <= n; i++) {
            scanf("%Lf%*d%*d%Lf", &r[i], &z[i]);
            r[i] *= 0.001; z[i] *= 0.001;
            v -= getballv(r[i]);
        }
        for(int i = 1; i <= s; i++) {
            len[i] = cal(i * v / s);
        }
        for(int i = 1; i <= s; i++) {
            printf("%.10Lf\n", len[i] - len[i - 1]);
        }
    }
    return 0;
}
[CF16E]Fish 题解

[CF16E]Fish 题解

题目地址:Codeforces:Problem – 16E – C 

[ZJOI2015]地震后的幻想乡 题解

[ZJOI2015]地震后的幻想乡 题解

题目地址:洛谷:【P3343】[ZJOI2015]地震后的幻想乡 – 洛谷、B 

数学笔记:概率、期望

数学笔记:概率、期望

期望(Expectation)的定义

如果X是在概率空间 (\Omega, F, P) 中的随机变量,那么它的期望值\mathrm{E}(X)的定义是:
\mathrm{E}(X) = \int_\Omega X \mathrm{d}P
如果两个随机变量的分布相同,则它们的期望值也相同。
离散型:
如果X是离散的随机变量,输出值为x_1, x_2, \ldots,和输出值相应的概率为p_1, p_2, \ldots(概率和为1)。若级数\sum_i p_ix_i绝对收敛,那么期望值\mathrm{E}(X)是一个无限数列的和:
\mathrm{E}(X) = \sum_i p_ix_i
连续型:
如果X是连续的随机变量,存在一个相应的概率密度函数f(x),若积分\int_{-\infty}^\infty xf(x) \mathrm{d}x绝对收敛,那么X的期望值可以计算为:
\mathrm{E}(X) = \int_{-\infty}^\infty xf(x) \mathrm{d}x

期望的性质

  1. \mathrm{E}(K) = K,K是任意实数
  2. \mathrm{E}(KX) = K\mathrm{E}(X),X是随机变量,K是任意实数
  3. \mathrm{E}(X+Y) = \mathrm{E}(X) + \mathrm{E}(Y),X和Y是在同一概率空间的两个随机变量
  4. 如果X和Y独立,则\mathrm{E}(XY) = \mathrm{E}(X)\mathrm{E}(Y)
  5. \mathrm{E}(X) = \mathrm{E}(\mathrm{E}(X|Y))

随机变量的独立与相关

两个事件A和B是独立的当且仅当\mathrm{P}(A, B) = \mathrm{P}(A)\mathrm{P}(B)
\mathrm{E}(XY) = \mathrm{E}(X)\mathrm{E}(Y)成立时,随机变量X和Y的协方差为0,又称它们不相关。
不相关的两个随机变量不一定独立。

全概率公式(Law of total probability)

假设{Bn: n = 1, 2, 3, …}是一个概率空间的有限或者可数无限的分割(既Bn为一完备事件组),且每个集合Bn是一个可测集合,则对任意事件A有全概率公式:
\mathrm{P}(A) = \sum_n \mathrm{P}(A, B_n)
又可以写成
\mathrm{P}(A) = \sum_n \mathrm{P}(A | B_n) \mathrm{P}(B_n)
还有
\mathrm{P}(A) = \mathrm{E}(\mathrm{P}(A | N))
此处N是任意随机变量。

全期望公式(Law of total expectation)

设X,Y为随机变量,下列期望和条件期望均存在,则
\mathrm{E}(X) = \mathrm{E}(\mathrm{E}(X|Y))
以及
\mathrm{E}(X) = \sum_i \mathrm{E}(X|A_i) \mathrm{P}(A_i)

贝叶斯定理(Bayes’ theorem)

\mathrm{P}(A, B) = \mathrm{P}(A)\mathrm{P}(B|A) = \mathrm{P}(B)\mathrm{P}(A|B)
因此有
\mathrm{P}(B|A) = \frac{\mathrm{P}(B)\mathrm{P}(A|B)}{\mathrm{P}(A)}

先验概率和后验概率

在贝叶斯统计中,某一不确定量p的先验概率分布是在考虑”观测数据”前,能表达p不确定性的概率分布;一个随机事件或者一个不确定事件的后验概率是在考虑和给出相关证据或数据后所得到的条件概率。
举个例子:有两个事件A与B,P(A|B)就是A的后验概率,而P(A, B)就是A的先验概率。
这两者的关系:P(A|B) = \frac{P(A, B)}{P(B)}
我们可以用先验概率和后验概率来定义先验期望等概念。

参考资料

拉格朗日插值法及其应用

拉格朗日插值法及其应用

概述 拉格朗日插值法常用于通过点值获得满足这些点值的多项式,是一种由点值到多项式的转换方式