[洛谷1919]【模板】A*B Problem升级版(FFT快速傅里叶) 题解
题目地址:洛谷:【P1919】【模板】A*B Problem升级版(FFT快速傅里叶) & …
May all the beauty be blessed.
一个m \times n的矩阵是一个由m行n列元素排列成的矩形阵列。元素可以是数字、符号或数学式。
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}。
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}
记法:矩阵\mathbf{A}的行列式可以记作|\mathbf{A}|或\mathrm{det}(\mathbf{A})。也可以直观地把矩阵的方括号换成垂直线表示。
直观定义:参见行列式 – 维基百科,自由的百科全书。
2阶矩阵的行列式:\begin{vmatrix} a & b \\ c & d \end{vmatrix} = ad - bc
3阶矩阵的行列式:主对角线乘积之和减副对角线元素乘积之和
几何意义:行向量/列向量张成的体积/面积。
更多内容参见行列式 – 维基百科,自由的百科全书。
范德蒙矩阵是一个各列呈现出几何级数关系的矩阵,例如
\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})不为零。
题目地址: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;
}