模拟赛

T2

考虑像之前那道题一样将折线图画出来

然后利用JOI那题的trick，枚举最后一次被 clear 的位置在哪里

我们发现 clear 的充要条件是最高进制位被消去，只要没有被 clear 则后半部分的最高位置就是折线图的最高位

那么次高位呢？我们发现当我们确定最高位过后，那么第一个 $1$ 的位置就无关紧要了，所以以它+1的位置作为新的原点建坐标系，递归上述过程即可

如何统计答案呢？我们考虑枚举每一位，于是问题就变成了“答案前缀为 1010101******” 的方案数

如何控制前缀为这个呢？其实也就是通过计算出

算了先去部分分了

对于 1-6 的点直接暴力 $f_{i,j}$ 即可，当处理询问时则处理一个前缀的答案和一个后缀的答案，考虑从此处用 0 进行合并，时间复杂度 $O(n2^k)$

对于 $7-14$ 的点，我们发现这样子是支持 $O(n^2k)$ 的

T3

求

$$\left( \sum_{i=1}^{n} f(a,b,i) \right) \mod{998244353}$$

其中 $f(a,b,i)$ 表示 $ax \equiv b \pmod{i}$ 的最小整数解

对于 $f(a,b,i)$ ，我们正常的求法是先判断是否有 $gcd(a,i) \mid b$ ，然后再用 $exgcd$ 求解

所以转化为求出 $ax+ik=gcd(a,i)$ 的最小整数解，设其为 $g(a,i)$，然后将其乘上 $\frac{b}{gcd(a,i)}$

所以先令，转化为

$$\begin{eqnarray}&& \sum_{i=1}^{n}[gcd(a,i)\mid b]g(a,i)\times \frac{b}{gcd(a,i)}\end{eqnarray}$$

![[sol(3).pdf]]

Upd

T2

因为每次操作只会对其后缀一段进行修改，所以理论上来说必须先修改后边的元素才能修改前边的

由于只有两种元素，所以每一位非 $0$ 则 $1$ ，而且最终答案只与其与 $r$ 的大小比较有关，所以我们可以考虑设状态转移方程 $f_{i,j,k}$ 表示当前在第 $i$ 位，当前与 $r$ 的LCP长度为 $j$ ，且LCP后半部分(不包括LCP+1)内 $1$ 的个数为 $k$ 的方案数

我么发现通过记录LCP我们就顺带着知道了前缀的模样，以及其与 $r$ 的大小关系

什么时候LCP的长度会增加呢？发现当且仅当正好补满或正好为空时

值得注意的是，LCP的增加的确是每次+1的，但是LCP的减少一次却不一定只减去1

所以最好的办法还是预处理一个转移矩阵或是什么东西

然后就做完了？

转来转去的，好麻烦

改成表示从右往左数第一个不相同的位置的左边一个点吧

我操了，好恶心

在这里讨论一下吧

首先是添加 $0$ 的情况，假设 lp,cnt

当 lp=0 ，