![[ZJOI2014]力 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180327c.jpg "180327c")
[ZJOI2014]力 题解
题目地址：ė …
标签： 数学
![[洛谷4245]【模板】MTT 题解 & 任意模数卷积算法（MTT）原理与实现](https://ksmeow.moe/wp-content/uploads/2018/03/180327b-720x400.jpg "180327b")
快速数论变换（NTT）原理及实现
概述
上次写了一篇狗屎文章快速傅里叶变换（FFT）原理与实现 | KSkun’s Blog，中间的FFT过程使用复数实现，由于使用浮点数存在精度误差。有什么应用于整数没有精度误差的方法吗？就是NTT了。
在NTT中，过程大致与FFT相同，只是用原根来代替单位根的作用。
原根？
你需要的数学姿势是：数学笔记：数论（欧拉函数、阶、原根） | KSkun’s Blog
为什么原根能够代替单位根？因为单位根具有的性质原根也可以具有。
证明参见：快速数论变换 (NTT) – riteme.site
实现？
大致与FFT相同。不同点大致就是要到处取模以及使用逆元操作。
代码？
本代码能够通过【P3803】【模板】多项式乘法（FFT） – 洛谷一题。代码中默认模数为998244353，一个原根为3。
// Code by KSkun, 2018/3
#include <cstdio>
#include <algorithm>
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;
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 = 1 << 22, G = 3, MO = 998244353;
int n, m, len, rev[MAXN];
LL a[MAXN], b[MAXN];
inline LL fpow(LL n, LL k) {
LL t = 1;
while(k) {
if(k & 1) t = (t * n) % MO;
n = (n * n) % MO;
k >>= 1;
}
return t;
}
inline void ntt(LL *arr, int f) {
for(int i = 0; i < n; i++) {
if(i < rev[i]) std::swap(arr[i], arr[rev[i]]);
}
for(int i = 1; i < n; i <<= 1) {
LL gn = fpow(G, (MO - 1) / (i << 1));
if(f == -1) gn = fpow(gn, MO - 2);
for(int j = 0; j < n; j += i << 1) {
LL w = 1;
for(int k = 0; k < i; k++) {
LL x = arr[j + k], y = w * arr[j + k + i] % MO;
arr[j + k] = (x + y) % MO;
arr[j + k + i] = ((x - y) % MO + MO) % MO;
w = (w * gn) % MO;
}
}
}
}
int main() {
n = readint(); m = readint();
for(int i = 0; i <= n; i++) {
a[i] = readint();
}
for(int i = 0; i <= m; i++) {
b[i] = readint();
}
m += n;
for(n = 1; n <= m; n <<= 1) len++;
for(int i = 0; i < n; i++) {
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (len - 1));
}
ntt(a, 1);
ntt(b, 1);
for(int i = 0; i <= n; i++) {
a[i] = (a[i] * b[i]) % MO;
}
ntt(a, -1);
int invn = fpow(n, MO - 2);
for(int i = 0; i <= m; i++) {
printf("%lld ", a[i] * invn % MO);
}
return 0;
}
![[洛谷1919]【模板】A*B Problem升级版（FFT快速傅里叶） 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180326d-471x400.jpg "180326d")
数学笔记：矩阵、行列式
矩阵（Matrix）
一个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}。
单位矩阵（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})不为零。
参考资料
![[CF364D]Ghd 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180325a-403x400.jpg "180325a")
![[WF2015]Cutting Cheese 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180324b.jpg "180324b")
[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 题解](https://ksmeow.moe/wp-content/uploads/2018/03/180324a.jpg "180324a")
