20241024

T1

感觉和最长上升子序列很像

求一个子序列，使得满足 $a’ib_i<a’{i+1}$

取个对数？然后就变成了 $\ln a’ib_i<\ln a’{i+1}$

也就是 $\ln a’i+\ln b_i<\ln a’{i+1}$

变成了加法，感觉会好做一点

现在变成了加上一个权值的最长上升子序列

考虑在正常的最长上升子序列中，我们设 $f_i$ 表示长度为 $i$ 的子序列的最小最后一位值

之所以能够这样维护还是因为 $f_i$ 具有单调性

但考虑对于现在而言，这还带有单调性吗？

显然具有，而且比之前的更强，要求在加上一个权值后仍旧比上一位要大

注意 $f_i$ 具有单调性，但由于有 $f_{i+1}>f_i+b_i$，所以 $f_i+b_i$ 也具有单调性

然后二分，应该就做完了？

T2

转化下题意，其实就是问存在多少个 $x,y$ 使得
$$
d(x-1)+y \equiv a \pmod{w}\

d(y-1)+x \equiv b \pmod{w}\

$$
$a,b$ 对 $w$ 取模，$1\le x,y \le min(m,d)$
$$
dx+y-d \equiv a \pmod{w}\

dy+x-d \equiv b \pmod{w}\

(d+1)y+(d+1)x\equiv a+b+2d \pmod{w}\

x+y\equiv \frac{a+b+2d}{(d+1)} \pmod{w}\

$$
当 $w$ 与 $d+1$ 互质时，设 $\frac{a+b+2d}{(d+1)}=D,min(m,d)=M$

则答案即为
$$
\sum_{x=1}^{M}\sum_{y=1}^{M}[w \mid x+y-D]\

\sum_{k=0}^{\frac{D+2}{w}}\sum_{x=1}^{M}\sum_{y=1}^{M}[x+y-D=kw]\

\sum_{k=0}^{\frac{D+2}{w}}\sum_{x=1}^{M} [1 \le kw+D-x \le M]\

\sum_{k=0}^{\frac{D+2}{w}}\sum_{x=1}^{M} [kw+D-M \le x \le kw+D-1]\

\sum_{x=1}^{M}\sum_{k=0}^{\frac{D+2}{w}} [kw+D-M \le x \le kw+D-1]\

$$
二分左右完全包含区间

同样的，我们还有
$$
dx+y-d \equiv a \pmod{w}\

dy+x-d \equiv b \pmod{w}\

(1-d)y+(d-1)x\equiv a-b \pmod{w}\

x-y\equiv \frac{a-b}{(d-1)} \pmod{w}\

$$

从头来，一定是哪里算错了
$$
dx+y \equiv a+d \pmod{w}\

dy+x \equiv b+d \pmod{w}\

$$
将 $d$ 对 $w$ 取模，得到 $D$

若 $D=0$ ，则此时是好算的

若 $D \not = 0$ ，则其与 $w$ 互质，变成了
$$
Dx+y \equiv a+D \pmod{w}\

Dy+x \equiv b+D \pmod{w}\

$$
不妨设 $y$ 是一个定值，那么有
$$
Dx \equiv a+D-y \pmod{w}\

x \equiv b+D-Dy \pmod{w}\

.\

Dx \equiv Y_1 \pmod{w}\

x \equiv Y_2 \pmod{w}\

$$
也就是说
$$
x \equiv \frac{Y_1}{D} \pmod{w}\

x \equiv Y_2 \pmod{w}\

$$
所以说当 $Y_1D^{-1}=Y_2$ 时，会产生 $\left\lfloor\frac{M-Y_2}{w} \right\rfloor +1$ 的贡献

设 $a+D=A$，$b+D=B$

那就是 $AD^{w-2}-yD^{w-2}\equiv B-Dy$

$AD^{w-2}-B\equiv (D^{w-2}+D)y$

所以说此时的答案即为
$$
\sum_{y=1}^{M}[(D^2-1)y \equiv a+(b-1)D+D^2](\left\lfloor\frac{M-(b+D-Dy)}{w} \right\rfloor +1)
$$
当 $$