前言

本来今天 sssy 把国庆前一天上课调到了今天，然后放 $8$ 天国庆，结果...

---

题目

同样的，好题放前面...

[ARC107D] Number of Multisets

Solution

非常好的一个动态规划题，开阔了视野...

看到数据，很容易可以先想到先设 $f_{i,j}$ 表示 $i$ 个元素的和为 $j$ 的方案数，接着难点就是考虑怎么转移；

分数很不好搞，最大是整数 $1$，不妨从这里先入手，若加入一个元素为 $1$ 的数，那么 $f_{i,j}=f_{i-1,j-1}$；

接下来就很巧妙了，我们不能局限于前一个状态 $i-1$，可以想想当前已知的状态也可不可以为我所用，由于每个元素只能为 ${\displaystyle \frac{1}{2_i}}$，那再从 $2$ 的倍数入手，可以发现 $f_{i,j}$ 其实也可以由 $f_{i,2\times j}$ 中的 $i$ 个元素同时除以 $2$ 得到，即 $f_{i,j}+=f_{i,2\times j}$。

最后留下一个问题，怎么证明这个转移方程是不重不漏的：

不重：由 $f_{i,j}=f_{i-1,j-1}$，可以知道当前已知的状态中的序列都是有 $1$ 的，所以由 $f_{i,2\times j}$ 同时除以 $2$ 的序列中肯定不会存在 $1$，所以不会有重复。

不漏：本蒟蒻太弱了，呜呜呜...

---

某题

闲话

• 考场已经推出性质了，为什么要卡我线段树...

• st表忘了怎么办...

题意

给定一个长度为 $n$ 的序列 $a$，问满足如下条件的区间 $[l,r]$ 的个数：

令 $x=a_l\wedge a_{l+1}\wedge \cdots \wedge a_r$，令 $y=a[l]\vee a[l+1]\vee a[l+2]\vee \cdots \vee a[r]$，满足 $2^{k1}\le x\oplus y<2^{k2}$，其中保证 $k1,k2$ 为整数。

Solution

这很水啊，主要要想到用二分...

首先看到要求一段区间的“与”和“或”，那明显可以用线段树维护（考场是这样想的），其实最后处理这题最优的是st表，因为没有修改操作...

普遍都会确定一个点 $r$，再找点 $l$ 的位置，对答案就会增加 $r-l+1$ 点贡献...

• tip：$x\oplus y=x\vee y-x\wedge y$

区间的或肯定会增加，其的与肯定会减少，那么由上面的 tip 可以知道 $x\oplus y$ 一定会增加，说明有单调性，那么跑两次二分确定上下界就可以了。

虽然我没想到这个 tip（忘了），不过没关系，我还是推出来了，考虑拆位处理，再分别想“或”部分和“与”部分，结合“异或”处理找规律即可啦！也许今天能推出来，以后不一定了（bushi，所以还是记住 tip 吧！

线段树+二分：$O(nloglogn)$

st表+二分：$O(nlogn)$

最后我想说，位运算的题拆位真的很好做...

---

[ABC285E] Work or Rest

闲话

首先是看错题，然后是纠结于前一周的最后一个假期对这个周第一个假期的影响，最后发现想多了...

Solution

用手模拟模拟，可以发现对于两个假期 $l$ 和 $r$，其中的贡献值是连续的，有规律的，可以直接用前缀和维护区间的权值；

然后直接一个普通的dp求解，现在还有一个问题：

• 一周的最后一个假期对这个周第一个假期的影响怎么解决。

观察一下又可以发现假期所在的位置其实不影响最后的答案，所以我们可以把所有假期都往前移，将第一个假期移到第一天就好处理了。

别忘了还要加上最后一个假期后的工作日的贡献。

---

SP9650 TRIPINV - Mega Inversions

同题：CF61E Enemy is weak

只不过要加个离散化...

zsq出的题其实不是这道，但差不多，把本题中的大于改为小于罢了。

Solution

按照这题讲吧，比较板了吧，要求 $i<j<k$ 且 $a_i>a_j>a_k$，一眼可以想到开两棵线段树优化动态规划（其实也不用动态规划思想，是我太弱）...