【模拟赛】20190612
nekko
2019-06-12 17:44:29
# 1. Inverse
首先一个比较显然的想法就是考虑所有点对的贡献
也就是只需要计算 $f_{k,x,y}$ 表示第一个元素在 $x$，第二个元素在 $y$，执行了 $k$ 次后 $x'<y'$ 的概率，很可惜它是 $O(kn^4)$ 的
设 $g(n)=\frac{n \cdot (n+1)}{2}$
首先考虑 $i<j$
---
一共有如下几类：
## $r < i < j \lor i < j < l \lor i < l \le r < j$
这一类中，$i,j$ 不会变，即：
$$f_{i,j} \cdot \left( g(i-1)+g(n-j)+g(j-i-1) \right)$$
``` cpp
upd(f[t][i][j], f[t - 1][i][j] * (g(i - 1) + g(n - j) + g(j - i - 1)) % mod);
```
## $l \le i \le r < j$
设 $S_n=\sum_{i=1}^{n}f_{i,j}$，以及它的前缀和 $T_n=\sum_{i=1}^{n}S_i$
F这一类中，$j$ 不会变，$i$ 会被映射到 $l+r-i$，即：
$$ \begin{aligned} &\sum_{l=1}^{i}\sum_{r=i}^{j-1} f_{l+r-i,j} \\ =&\sum_{l=1}^{i}S_{l+j-i-1}-S_{l-1} \\ =&T_{j-1}-T_{j-i-1}-T_{i-1} \end{aligned} $$
``` cpp
upd(f[t][i][j], col[j][j - 1] - col[j][j - i - 1] - col[j][i - 1]);
```
## $i < l \le j \le r$
设 $S_n=\sum_{j=1}^{n}f_{i,j}$，以及它的前缀和 $T_n=\sum_{j=1}^{n}S_j$
这一类中，$i$ 不会变，$j$ 会被映射到 $l+r-j$，即：
$$ \begin{aligned} &\sum_{l=i+1}^{j}\sum_{r=j}^{n} f_{i,l+r-j} \\ =&\sum_{l=i+1}^{j} S_{l+n-j}-S_{l-1} \\ =&T_{n}-T_{i+n-j}-T_{j-1}+T_{i-1} \end{aligned} $$
``` cpp
upd(f[t][i][j], row[i][n] - row[i][i + n - j] - row[i][j - 1] + row[i][i - 1]);
```
## $l \le i < j \le r$
设 $h_{i,j}=f_{i,i-j}$
设 $S_n=\sum_{k=1}^{n}h_{k,i-j}$，以及它的前缀和 $T_n=\sum_{k=1}^{n}S_k$
这一类中，$i,j$ 分别会变为 $l+r-i,l+r-j$，则：
$$ \begin{aligned} &\sum_{l=1}^{i}\sum_{r=j}^{n} f_{l+r-i,l+r-j} \\ =&\sum_{l=1}^{i}\sum_{r=j}^{n} h_{l+r-i,j-i} \\ =&\sum_{l=1}^{i} S_{l+n-i}-S_{l+j-i-1} \\ =&T_{n}-T_{n-i}-T_{j-1}+T_{j-i-1} \end{aligned} $$
``` cpp
upd(f[t][i][j], h_col[j - i][n] - h_col[j - i][n - i] - h_col[j - i][j - 1] + h_col[j - i][j - i - 1]);
```
---
之后考虑 $i>j$，实际上是一样的，把之前的 $i,j$ 互换位置即可
## $r < j < i \lor j < i < l \lor j < l \le r < i$
这一类中，$i,j$ 不会变，即：
$$f_{i,j} \cdot \left( g(j-1)+g(n-i)+g(i-j-1) \right)$$
``` cpp
upd(f[t][i][j], f[t - 1][i][j] * (g(j - 1) + g(n - i) + g(i - j - 1)) % mod);
```
## $l \le j \le r < i$
设 $S_n=\sum_{j=1}^{n}f_{i,j}$，以及它的前缀和 $T_n=\sum_{j=1}^{n}S_j$
这一类中，$i$ 不会变，$j$ 会被映射到 $l+r-j$，即：
$$ \begin{aligned} &\sum_{l=1}^{j}\sum_{r=j}^{i-1} f_{i,l+r-j} \\ =&\sum_{l=1}^{j} S_{l+i-j-1}-S_{l-1} \\ =&T_{i-1}-T_{i-j-1}-T_{j-1} \\ \end{aligned} $$
``` cpp
upd(f[t][i][j], row[i][i - 1] - row[i][i - j - 1] - row[i][j - 1]);
```
## $j < l \le i \le r$
设 $S_n=\sum_{i=1}^{n}f_{i,j}$，以及它的前缀和 $T_n=\sum_{i=1}^{n}S_i$
这一类中，$j$ 不会变，$i$ 会被映射到 $l+r-i$，即：
$$ \begin{aligned} &\sum_{l=j+1}^{i}\sum_{r=i}^{n} f_{l+r-i,j} \\ =&\sum_{l=j+1}^{i} S_{l+n-i}-S_{l-1} \\ =&\sum_{l=i+1}^{j} S_{l+n-j}-S_{l-1} \\ =&T_{n}-T_{j+n-i}-T_{i-1}+T_{j-1} \\ \end{aligned} $$
``` cpp
upd(f[t][i][j], col[j][n] - col[j][j + n - i] - col[j][i - 1] + col[j][j - 1]);
```
## $l \le j < i \le r$
设 $h_{i,j}=f_{j-i,j}$
设 $S_n=\sum_{k=1}^{n}h_{i-j,k}$，以及它的前缀和 $T_n=\sum_{k=1}^{n}S_k$
这一类中，$i,j$ 分别会变为 $l+r-i,l+r-j$，则：
$$ \begin{aligned} &\sum_{l=1}^{j}\sum_{r=i}^{n} f_{l+r-i,l+r-j} \\ =&\sum_{l=1}^{j}\sum_{r=i}^{n} h_{i-j,l+r-j} \\ =&\sum_{l=1}^{j} S_{l+n-j} - S_{l+i-j-1} \\ =&T_{n}-T_{n-j}-T_{i-1}+T_{i-j-1} \end{aligned} $$
``` cpp
upd(f[t][i][j], h_row[i - j][n] - h_row[i - j][n - j] - h_row[i - j][i - 1] + h_row[i - j][i - j - 1]);
```
# 2. Subsequence
# 3. Convex
只需要把 $s<\frac{S}{2}$ 的带上 $-1$ 加起来，然后把 $s>\frac{S}{2}$ 的带上 $1$ 加起来就行了
那么只需要维护面积的前缀和就行了，于是只需要考虑到叉积前缀和，那么就是：
$$ \begin{aligned} &\sum_{k=i+2}^{j} (p_{i_x}-p_{k_x},p_{i_y}-p_{k_y}) \times (p_{0_x}-p_{k_x},p_{0_y}-p_{k_y}) \\ =&\sum_{k=i+2}^{j} (p_{i_x}-p_{k_x}) \times (p_{0_y}-p_{k_y}) - (p_{0_x}-p_{k_x}) \times (p_{i_y}-p_{k_y}) \\ &x_0=p_{0_x},y_0=p_{0_y},x_1=p_{i_x},y_1=p_{i_y},x=p_{k_x},y=p_{k_y}\\ =&\sum_{k=i+2}^{j} (x_1-x)(y_0-y)-(x_0-x)(y_1-y) \\ =&x_1y_0+xy-xy_0-x_1y-x_0y_1-xy+xy_1+x_0y \\ =&(x_1y_0-x_0y_1)+x(y_1-y_0)+y(x_0-x_1) \end{aligned} $$
显然 $n=2 \cdot 10^6$ 的时候 $O(n \log n)$ 可以过的，所以不需要去写双指针了