ACGO挑战赛#10
来源：出题人wtcqwq题解
T1、YTIROIRP
按题目模拟即可。
这道题需要注意位运算的优先级很低，远低于四则运算。
换句话说 1+1|2 被理解为 2|2=2，尽管你可能想写的是 1+(1|2)=1+3=4。
关于人名，Ytiroirp 反过来写，即 priority ，含义为优先，就在提示你易错点。
T2、ELBISIVID
题目大意：站在数轴原点，可以走任意不是 kkk 倍数的步幅，求最小步数走到点 xxx。
题解：如果 xxx 是 kkk 的倍数，你先走 111，转化成不是 kkk 的倍数即可。
如果 xxx 不是 kkk 的倍数，直接走即可。
换句话说，答案至多为 222。
与上题类似的，Elbisivid 反转即为 divisible，也是本题题意&解题方法的关键。
T3、LSCUMM
容易想到，可以用两个互质的 NNN 的因数使得 lcm 为 NNN。由于对序列长度没有限制，所以剩下的都用 111 来填充使得和达到 NNN。所以问题就转化成了判断 NNN 有没有两个互质的因数。
T4、DISTINCT
考虑改变钦定顺序，从 aia_iai 小往大钦定。
显然前面选过的一定会对当前可以选的数量造成影响。
所以将 aia_iai 排序后，答案即为 ∏(ai−i+1)\prod (a_i-i+1)∏(ai −i+1)。
T5、DLOONC
1. 如果要想让火炉燃烧时间少，就得在无客人到访的时候熄灭。
2. 如果要想让火炉燃烧时间更少，就得让所有的火柴都用上，也就是尽可能多的打开熄灭。
3. 如果要想让火炉燃烧的时间最少，就得在客人到访时间间隔最长的时候熄灭，打开火炉。
总而言之，让每次打开熄灭，让每根火柴发挥最大用处。
如果中途不熄灭炉火，从第一位客人来访到最后一位客人离开，炉火运行时间是： an−a1+1a_{n}-a_{1}+1an −a1 +1 。(因为第一位客人到访后还有1的访问时间)
贪心算法，就要尽可能的在时间间隔大两次访问之间熄灭炉火，所以也要推导出访问间隔公式： ai+1−ai−1a_{i+1}-a_{i}-1ai+1 −ai −1。(因为其中夹杂着第一位客人的到访时间）
把间隔时间存储在数组里，用 sort 从大到小排序，在依照火柴数量减去相应的间隔时间。
T6、PTORRWEEE
考虑欧拉序，在欧拉序（dfs 序）下，子树是连续区间。
考虑怎么处理 dis(u,v)dis(u,v)dis(u,v) 的约束，可以制约成 dv−dud_v-d_udv −du ，也就是 dv−du+xd_v-d_u+xdv −du +x。
整个式子就是 adv−du+xa^{d_v-d_u+x}adv −du +x ，可以拆分成 advax−dua^{d_v}a^{x-d_u}adv ax−du 。
对于每一个点 vvv，前一项是可以提出来的。所以只需要加后面的 ax−dua^{x-d_u}ax−du 即可。转化成一般的子树加问题，用欧拉序+树状数组解决。
又，因为 dud_udu 有可能 >x>x>x，需要处理分数取模问题。
