id1

[CF1677F] Tokitsukaze and Gems

题意：

$a_{1\sim n}$ $G(l,r)=[0,0,\cdots,a_l,a_{l+1},\cdots,a_{r-1}, a_r,0,0,\cdots,0]$ $n,k\le 10^5,p^2\not=1,a_i\le 998244352$ ，求：
$\sum_{l=1}^n\sum_{r=l}^n\sum_{[t_1,t_2,\cdots,t_n]\subseteq G(l,r)}\left(\sum_{i=1}^n[t_i>0]\right)\cdot\left(\sum_{i=1}^np^{t_i}\cdot t_i^k\right) \pmod{998244353}$

题解：

$i$ 的贡献，得到：

\begin{aligned} \mathrm{Ans}&=\sum_{i=1}^n\left( \sum_{j=1}^{a_i}p^i\cdot i^k \right)\cdot \sum_{l=1}^i\sum_{r=i}^ncalc(l,r,i)\\ &=\sum_{i=1}^n\left( \sum_{j=1}^{a_i}p^i\cdot i^k \right)\cdot \left( x\cdot \left(\sum_{j=i}^n{\prod_{q=i+1}^j(1+a_qx)}\right)\cdot \left(\sum_{j=1}^i{\prod_{q=j}^{i-1}(1+a_qx)}\right) \right)'(1) \end{aligned}

$(f(1),f'(1))$ $(g(1),g'(1))$ $((f\times g)(1), (f\times g)'(1))=(f(1)\cdot g(1),f(1)\cdot g'(1)+f'(1)+g(1))$ $\sum_{j=1}^{a_i}p^i\cdot i^k$ ，事情就交给 EI 科技了。

[CF1666K] Kingdom Partition

题意：

$n$ $m$ A/B/C $a$ A $b$ 点为 B），代价为每条边的代价的和，每条边的代价计算方式如下：
A B C
A $2w$ $0$ $w$
B $0$ $2w$ $w$
C $w$ $w$ $0$

	A	B	C
A	$2w$	$0$	$w$
B	$0$	$2w$	$w$
C	$w$	$w$	$0$

人类智慧题解：

$(u,v)\rightarrow(u,v')+(u',v)$ ，那么看看这张新图的贡献表：

	ST	TS	SS	TT
ST	$2$		$1$	$1$
TS		$2$	$1$	$1$
SS	$1$	$1$		$2$
TT	$1$	$1$	$2$

$ST=A$ $TS=B$ $SS=C$ $TT=C$ $SS-TT$ $TT-SS$ $TT$ $SS$ $TT$ $SS$ $O(\mathrm{dinic})$ 。

[agc051e] Middle Point

题意：

$n$ $\vec{v_{1\sim n}}$ $10^9$ ，保证任意三点不共线。

题解：

check $(X,Y)$ 是否可以 plot。有三个条件要满足：

在初始点构成的凸包内。
若在凸包的边界上，那么容易判断并数出来。
非负整数 $w_{1\sim n}$ $k$ $\sum_{i=1}^nw_i\cdot \vec{v_i}=(X,Y)\cdot 2^k$ $\sum_{i=1}^n w_i=2^k$ 。

第三个条件是最为棘手的，rng_58整数 $w_{1\sim n}$ $\sum_{i=1}^n w_i\cdot \vec{v_i}=(X,Y)$ $\sum_{i=1}^nw_i=1$ $a_i\leftarrow a_i-a_1,a_1\leftarrow 0$ $w_1$ $\sum_{i=1}^nw_i=1$ [CERC2015]Looping Labyrinth $\{(X,Y)\}$ $a\vec{i}+b\vec{j}$ $\vec{i}$ $\vec{j}$ ，下面介绍一个更为简洁的办法：

$\vec{i},\vec{j}$ $\vec{k}$ $(0,0)$ $\left|\vec{i}+\lambda\vec{j}\right|<\max\left(\left|\vec{i}\right|,\left|\vec{j}\right|\right)$ $\vec{j}\leftarrow \vec{i}+\lambda\vec{j}$ $O\left(\log{\left|\mathrm{MAX}\right|}\right)$ 的时间内完成增量（Thanks https://codeforces.com/blog/entry/86100 @ecnerwala）。

$x\vec{i}+y\vec{j}$ $2$ $x\vec{i'}+y\vec{j'}$ 来说，只有整数点满足 [第三个条件]：


xxxxxxxxxx
9
1
for (int i = 1; i <= 100; i++)
2
{
3
    while (bs[1].x % 2 == 0 && bs[1].y % 2 == 0) bs[1].x /= 2, bs[1].y /= 2;
4
    while (bs[2].x % 2 == 0 && bs[2].y % 2 == 0) bs[2].x /= 2, bs[2].y /= 2;
5
    if ((bs[1] + bs[2]).x % 2 == 0 && (bs[1] + bs[2]).y % 2 == 0)
6
    {
7
        auto e1 = bs[1] + bs[2], e2 = bs[1] - bs[2]; bs[1] = e1, bs[2] = e2;
8
    }
9
}

$S=n+\frac s2-1$ $O(n\log{U})$ 。