real: 68 + 0 + 0

expect: 100 + 40 + 0

T1 被卡常了,T2 被输入埋了

links

sol

# 简单最优化问题

​ 枚举个gcdgcd ,使用 DirichletDirichlet 前缀和优化。

# 简单数学题

​ 一种题解做法是枚举第 ii 个位置有贡献然后使用积分。

​ 实际上可以下一步转换不必使用积分,而是考虑每个位置,他们的可取值域要每次相对来说会乘一个阶乘,而给他们任意取值后每个位置成为最大值的机会均等,然后就可以推出柿子:

Ans=i=1n(i1)!iiAns= \sum_{i=1}^n {(i-1)!\over i^i}

上面那个 (i1)!(i-1)! 就是乘了一个 1n1\over n 后的剩余结果。

这个柿子直接 O(nlogn)\mathrm O(n\mathrm log n) 即可做到 40pts ,我们考虑线性做法,就是要快速算出 iii^i 。利用原根,我们知道 ii=gi×loggii^i=g^{i\times \mathrm{log_gi}}

然后 loggi\mathrm {log}_gi 扫一遍就好

这题 tm 卡常,奇技淫巧我也不会。

# 简单数据结构题

考虑如果我们知道一个点子树内所有数字权值的 bitset\texttt{bitset} ,如果是手写的,我们很容易求出答案即 val(sd)&val(sd+k)val(sd)\&val(sd+k)val(x)val(x) 表示取 xx6464 位。

考虑优化,显然可以按 dfndfn 序分块,我们可以预处理两两块之间的 bitset\texttt{bitset} ,然后这题卡空间,于是利用 dfndfn 的性质,两两子树区间只可能包含或不交,于是我们要处理的相当于是一棵 二叉树上的所有节点,叶子有 BB 个,也就是 2B2B 个区间,之间预处理就好。

题解的分块方式是在树上选一些点为关键点,处理他们子树中的 bitset\texttt{bitset} ,若一个点 uu 内子树最大一个被处理过的关键点 mxmx 使得 sizusizmxBsiz_u-siz_{mx} \ge B ,你就把这个点也给染黑。

由于这题 tmd 卡空间,所以需要调参卡一下块长。

出题人诚实谦卑。

更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

Odalys 微信支付

微信支付

Odalys 支付宝

支付宝