23/3/6
小模拟，eezz。
23/3/7
谔谔
考虑一条链的第一问，计算钦定这条链上所有点权都 \(\in [l,l+K]\) 且最小值 \(=l\) 的方案数。
显然可以先容斥转化为 $\ \ $ 所有点权都 \(\in [l,l+K]\)的方案数 $\ \ $ 减去 $\ \ $ 所有点权都 \(\in [l+1,l+K]\)的方案数。
设 \(f(l,r)\) 表示所有点权都 \(\in [l,l+r]\)的方案数，那么对于这条链，答案就是 \(\sum_lf(l,l+K)-f(l+1,l+K)=\sum_lf(l,l+K)-\sum_lf(l+1,l+K)\)。
现在考虑求 \(\sum_lf(l,l+K)\)。
首先，对于一个点 \([l_i,r_i]\)，它能取的数的个数为 \(| [l_i,r_i] \cap [l,l+K]|\)
当 \([l,l+K]\) 右移一位变为 \([l+1,l+K+1]\) 时，一个点能取的数个数只会有 +1，不变或者 -1 三种状态。
于是移动这个区间的时候，每个点状态都不变的值域段有 \(O(n)\) 段。
每一段中一个 \(l\) 的贡献就是 $\prod(a_i \pm l) $，是一个关于 \(l\) 的多项式。
于是一段连续值域就相当于一个多项式的区间的值的和，转化为多项式前缀和，进行一个拉格朗日值的插。
那对于第二问，就是把 \(a_i \pm l\) 变成 \(a_i+xl+yl^2\)，变成一个二次的多项式，再插值复杂度仍是 \(O(n)\)。
Bonus：其实不用真的把多项式求出来，可以直接dp出一个点值。
BBounus：可恶的卡常。
end。
23/3/11
自己只能想到 \(O(m^2)\) 的费用流了，一写还出现了负环/ng，而且写挂了。。
寄寄寄
考虑性质 C：
直接把每个消息之间连有向边，有边 \((u,v)\) 表示消息 \(u\) 放在消息 \(v\)上面能产生贡献。
如果是 DAG 的话就万事大吉了，直接跑最小路径覆盖就行。
但是寄了，环一大堆。
但是由于性质 C，如果成环了则必定有：
-
环里没有学术信息
-
环里全是
loushang或全是louxia。
以上两条性质显然。
由于题目中反复强调的重要性质，我们可以不断地断环成链。具体方法如下：
假设有一个环 \(A_1 \to B_1 \to C_1 \to A_1\)（字母表示发出者），且 \(A\) 的学术消息是 \(a\)，当前接在 \(a\) 两侧的是 \(x \to a \to y\)（\(x\)，\(y\)均为一条链或者没有）。
那么我们就可以把环接到链上，形成 （楼上形的环）\(x \to A_1 \to B_1 \to C_1 \to a \to y\) 或 （楼下形的环）\(x \to a \to B_1 \to C_1 \to A_1 \to y\)，这两种方案显然合法且总贡献不变。
上面那个最小路径覆盖使用二分图做的，但是这样边数爆炸。
考虑优化建图，对人建出入两个虚点。u v louxia 的话 \(v\) 的出点连向这个消息的入点；u v loushang 的话这个消息的出点连向 \(v\) 的入点。
然后用残量网络先找出方案，接着用双向链表维护断环成链的过程，就好了。
然后是没有性质 C 的情况：
这个时候会出现 a b loushang 和 b a louxia。这个时候把这俩接起来一定不劣。于是可以合并成一个 \(a\) 进 \(b\) 出的学术消息。
写起来比较恶心，而且我又被卡常了/cf
来自题解的卡常技巧：把所有边类型反一反，输出倒序。
这说明了加边顺序对 Dinic 的极大影响（
原来我10天才能补完 Day1/cf
23/3/16
先来自己思路。
首先数都不超过 \(2000\)，所以 \(n \leq 10^6\) 显然是假的，直接同一个数合并。
然后考虑把每个数映射到一个和它质因子集合有关的东西上。
因为 \(s_i \leq 2000\)， 所以每个数最有一个质因子 \(\geq \sqrt{2000} ≈ 45\)，而 \(45\) 以下的质数只有 \(14\) 个，因此我们完全可以把每个数写成一个 \(14\) 位的二进制数加一个数（那个 \(\ge 45\) 的数）。
把用上述表示方法表示出来后相等的数搞成一个等价类，那么我们就可以用 \(num[pr][bit]\) 来表示那个 \(14\) 位的二进制数等于 \(bit\) 且那个大于 \(45\) 的质数是 \(pr\) 的数的个数。
接下来是询问。如果询问质数都 \(\leq 45\)，那么可以直接 \(dp\) 预处理所有的答案，\(O(2^{14} \times 2000)\)（因为最多只有2000个位置有值）。
如果有大于 \(45\) 的质数，那么每个这样的质数都要有至少一个数来满足，而一个数最多只会被一个这样的质数整除。
于是我们先预处理出 \(a[pr][B]\) 表示在 \(num[pr][*]\) 中选几个，使得这些数的 \(bit\) 或起来等于 \(B\) 的方案数。应该还是 \(O(2^{14} \times 2000)\)，理由同上。
然后就是喜闻乐见的FWT了。枚举 \(num[pr]\) 中选完数以后前 \(14\) 个质数的状态，算出方案数后配合上文的 \(dp\) 转化为质数都 \(\leq 45\) 的情况。而这个方案数就是每个 \(a[pr]\) 用 or 卷起来。
这下可以在外面处理完 \(a\) 以后直接 \(O(300*14*2^{14})\)（45以上大概300？个质数）FWT，然后在询问内 \(O(c_i*2^{14})\) 点乘，最后 \(O(m*2^{14}*14)\) 逆变换回原数列，完全可以。
好了好了，这下除了FWT都会了/cf/cf
Todo:
标签：pr,历年,14,记录,省选,质数,45,联考 From： https://www.cnblogs.com/jimmywang/p/17227841.html