[洛谷1919]【模板】A*B Problem升级版(FFT快速傅里叶) 题解
题目地址:洛谷:【P1919】【模板】A*B Problem升级版(FFT快速傅里叶) & …
May all the beauty be blessed.
一个[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]。
[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]
记法:矩阵[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阶矩阵的行列式:主对角线乘积之和减副对角线元素乘积之和
几何意义:行向量/列向量张成的体积/面积。
更多内容参见行列式 – 维基百科,自由的百科全书。
范德蒙矩阵是一个各列呈现出几何级数关系的矩阵,例如
[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]不为零。
题目地址:UVa:UVa Online Judge、洛谷:【UVA1712】Cutting Cheese – 洛谷
原题面参见UVa/vjudge。
给你一个100*100*100的大方块,里面有若干球形空缺,要求切成s个体积相同的小方块,求每一块的厚度。
简单的计算几何。
我们考虑球形体积和球缺体积的算法
[latex display=”true”]\begin{aligned} V_{\text{ball}} &= \frac{4}{3} \pi r^3 \\ V_{\text{cap}} &= \pi h^2 (r – \frac{h}{3}) \end{aligned}[/latex]
对于每一块,我们二分计算它与之前所有块加起来的厚度(因为这样只需要考虑切面的球缺),每次计算块体积的时候遍历球体,如果完全包含减体积,如果部分包含减球缺体积,
// 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;
}