构造与思维

由于构造与思维题想出来后编程复杂度接近与 $0$ ，于是开个合集

# CF468C Hack it!

定义 $f(x)$ 为 $x$ 各数位之和，构造一组 $l, r$ 使得 $\sum\limits_{i=l}^{r} f(i) \equiv 0 \pmod{a}$ ，其中 $a$ 为给定值。

$$a\le 10^{18}, l, r \le 10^{200}$$

# Solution:

发现 $f(x + 10^{18}) = f(x) + 1$

令 $\sum_{i=0}^{10^{18} - 1} f(i) \mod a = p$

然后整体右移，发现 $p + 1$ 。

然后就是手算了。

# [ARC089C] GraphXY

给定 $d_{i,j}$ 矩阵，要求构造一张无向图，边权为值 $v$ 或未知数 $x,y$ ，要求 $x=a,y=b$ 时你定的起点 $s$ ，终点 $t$ 最短路为 $d_{a,b}$ 。
$n,m\le 10, v\le 100$

# Solution:

不妨设 $f_{i,j}$ 表示最短路上有 $i$ 个 $x$ ，$j$ 个 $y$ 离 d_