1120

· · 个人记录

一.

题目描述

Solution

设f[i]表示最终X=i的方案数

考虑使X=i的必要条件为所有选择的p均满足i|a[p]

因此记录cnt[i]表示满足a[p]=i的p的个数，有：

f[i]=(\sum_{j=1}^{i*j<=m} {f[i*j]})^k

考虑到此时f[i]也包含了使X=ki即i的倍数的方案数，所以：

f[i]=(\sum_{j=1}^{i*j<=m} {f[i*j]})^k-\sum_{j=2}^{i*j<=m} {f[i*j]}

只需倒序枚举m，时间复杂度为O(mlnm)

二.

题目描述

考场错误思路: l~r对k取模后不代表l~r的最大值也会对k取模！！！

Solution

首先对于1，3操作，只需用线段树维护区间最大值即可。

对于2操作，较为暴力的方法是将区间[l,r]在线段树上下沉到叶节点，将叶节点数值mod k，再pushup即可，这样每次操作复杂度最差为O(n)

考虑到某节点时，节点下区间最大值小于k，则继续下传就无意义了。而每次取模至少将数值减少一半，因此每个点最多被取模logM次，总时间复杂度不超过O(nlogM)