沙发
by ddd @ 2017-01-30 22:23:19
#题解（二）
## Koishi Loves Construction
Task1：
通过爆搜观察发现，除了 $1$ 以外的奇数都无解，偶数都有解。
证明：由于 $n|n$ ，也就是说 $n$ 必须放于第一位，前缀和第一位一定是 $0$ ，奇数情况下又由于 $n|\frac{n(n+1)}{2}$ ，也就是说前缀和最后一位一定是 $0$ ，导致矛盾。
打表观察，每个偶数搜出来的方案都有 $n,1,n-2,3,n-4,5\cdots$ ，不难证明其正确性。
Task2：
通过爆搜观察发现，除了 $4$ 以外的合数都无解，质数都有解。
证明：考虑到 $n|n!$ ，那么前缀积的最后一项一定是 $0$ ，也就是说最后一项尽量放 $n$ ，那么这要求 $n\nmid(n-1)!$ ，发现只有 $4$ 和质数胜任这个要求。
打表观察，每个质数搜出来的前缀积方案都有 $1,2,3,4\cdots p$ ，也就是说第 $i$ 位就是 $\frac{i+1}{i}$ ，通过逆元算出来就可以了。1和4的情况特判即可。
## Koishi Loves Segments
被骂成原题了啊，可能是我题目做的太少的缘故，我真的没看过接近的题目啊QAQ
从左到右加入线段，当存在一个点不符合要求时，就删除掉覆盖了它的右端点最远的线段。这个可以离散化后用一个set维护线段集合做到。
好像所有选手写的都是区间减线段树模拟删除线段啊，我明明不是故意卡常的啊，为什么会这样子呢。
##Koishi Loves Number Theory
先列两个结论
- $gcd(x^n-1,x^m-1)=x^{gcd(n,m)}-1$
- $lcm(a_1,a_2,...a_N)=\frac{1元gcd之积*3元gcd之积...}{2元gcd之积*4元gcd之积...}$
结论1可以考虑辗转相除法证明，结论2可以考虑lcm的积性求质因子贡献，这里不详细展开。
$a_i$ 的范围很大，但它们的 $gcd$ 数量很少。开一个map维护每个gcd和它的贡献就没了啊。
剩下的就是暴力了
by Created_equal1 @ 2017-01-30 22:25:04
#题解（三）
##随机数生成器
首先如果两个询问区间为 $[l1,r1]$ 和 $[l2,r2]$ ，$[l2,r2]$ 被 $[l1,r1]$ 完全包含（$l1 \leq l2 \leq r2 \leq r1$），这样 $[l1,r1]$ 就废了（因为它的询问结果肯定较小），排序预处理一下就可以去掉所有这些没用的区间了。有用的区间左端点两两不同，而且按左端点排序，右端点就会严格递增。
我们考虑有限的期望公式，对于一个随机整数变量 $x \geq 0$ ，它的期望 $E(x)=\sum_{整数s\geq 1} P(x \geq s)$ 。
我们考虑如何暴力地求出 $P(x \geq s)$ ，直接算不是很方便，我们考虑计算 $1-P(x \leq s-1)$ 。
既然测试结果是这些询问得到的结果的最大值，那么只要保证每个询问结果都 $\leq s-1$ 就好了，即每个询问区间内都至少有一个数 $\leq s-1$ 。
考虑搞一个dp，我们用 $f[i][j]$ 表示考虑 $a_1...a_i$ 的时候能满足询问1~j的概率，前面排序后这个东西可以简单地dp出来。这样就能获得50分了！（感觉如果按这个思路也是能做满分的，不过出题人比较菜没有想出来）
考虑我们换一种思路来做，对于每个元素考虑它能满足哪些询问。我们可以发现满足的询问一定是一个连续区间，而且依次考虑每个元素得到的每个询问区间也是满足左端点右端点都不降的。
这样我们就把问题转化成了：有若干个区间，这些区间左右端点都不降，要覆盖整段，每个区间选的概率为p（ $p=\frac{s-1}{x}$ ），问覆盖全段的概率。
考虑用$f[i]$表示考虑前i个区间，选择第i个区间，覆盖1~i区间右端点的概率，它可以用前面任意一个与第i个区间有交集的区间来转移。
容易得到转移方程 $f[i]=p\times(\sum_{r[j] \geq l[i]-1} f[j]\times (1-p)^{i-j-1}+[l[i]=1](1-p)^{i-1})$ ，答案就是 $\sum_{r[i]=n} f[i]*(1-p)^{n-i}$ 。
考虑把f的转移方程写的美观一点； $f[i]=p\times(\sum_{r[j] \geq l[i]-1} f[j]\times (1-p)^{-j}\times(1-p)^{i-1}+[l[i]=1](1-p)^{i-1})$ ，这样我们大概可以用一个树状数组来维护 $f[j]\times (1-p)^{-j}$ ？
如果你真的这样写了70分，那么恭(ha)喜(ha)你(ha)了(ha)。既然l[i]、r[i]都不降，只要two-pointer一下就是线性的了。这样就过了。
其实 $x \leq 10^7$ 也是能做的，不过没(lan)什(de)么(xie)意(biao)思(cheng)就不出了。
##雪辉
如果是一个序列，每次询问区间的mex怎么做
分块，预处理任意两块之间的bitset，然后每个询问只需要加入 $log$ 个数就可以了，复杂度 $O( ( n + m )( \sqrt{ n } + n / 64 ) )$
树上同理
在树上选择 $\sqrt{ n }$ 个点当作关键点，有一个贪心的方法可以保证任意两个关键点之间的距离是 $O( \sqrt{ n } )$ 的
按深度从大到小枚举树上的每个点，将点x标记为关键点当且仅当 $x$ 的子树中有一个点到 $x$ 的距离大于 $\sqrt{ n }$ 且不为关键点
或者直接随机 $\sqrt{ n }$ 个点当作关键点也可以保证复杂度
考虑预处理关键点之间的bitset，发现不能套用序列上的做法，因为dfs涉及到撤销，如果套用序列上的做法就需要使用可持久化bitset，复杂度变为 $O( n^2 )$
考虑将原树重构为 $\sqrt{ n }$ 个点的新树，即只有关键点的新树
重构树中两点之间连有边当且仅当这两个关键点在原树中形成的链上没有其他关键点
重构树的边权是一个bitset，存有这两个关键点之间的数
通过这个新的树，可以在 $O( n( \sqrt{ n } + n / 64 ))$ 的时间预处理任意两点之间的bitset
每个询问是多个树链的并，那么可以搞出每个树链的bitset之后在把他们或起来
树链 $( x , y )$ 的答案即相当于 $( x , l )$ 的答案或 $( y , l )$ 的答案，$l$ 为 $x , y$ 的lca
至于为什么不能直接求 $( x , y )$ 的答案，因为预处理的两个点之间的bitset是相对于重构树的，有可能会加入多余的点
与序列上的处理方法相似，每个询问只需要加入 $\sqrt{ n }$ 个数即到达一个关键点
总复杂度 $O( ( n + m )( \sqrt{ n } + n / 64 ) )$
因为stl的bitset没法支持询问mex，所以要手写bitset
by Created_equal1 @ 2017-01-30 22:25:35
F题公式有误的部分：
by fjzzq2002 @ 2017-01-30 22:57:14
占楼+膜拜
by huhuhuhaha @ 2017-01-31 10:22:59
后排膜拜。
by fcba @ 2017-01-31 11:51:53
伪前排膜拜
by bcku1 @ 2017-01-31 14:00:46
问一下
签到题复杂度中，(r-l)\*log r的log 是怎么来的？
by fakeman @ 2017-01-31 16:39:42
另外能不能提供一下数据 XD
by fakeman @ 2017-01-31 16:45:06
%%%
by wh_ZH @ 2017-01-31 18:30:34