bnu-faraway/2018中国大学生程序设计竞赛 - 网络选拔赛

Info

Date:2018.08.25

Link

Solutions

A Buy and Resell

solved by gjy,sk


sk’s solution

经典的括号序列贪心,用个优先队列就行。

B Congruence equation

upsolved by gjy


由裴蜀定理,条件2等价于\(gcd(a_1,a_2,......,a_k,m)==1\),自然想到写成\(\mu \ast 1\)的形式。

对于存在非-1元素的序列,只需要枚举非-1元素gcd的约数即可。

对于全是-1的序列,对刚才的式子继续化简得到\[Ans = \sum_{d=1}^{n} \mu(d) \sum_{m=1}^{\lfloor \frac{n}{d} \rfloor} m^k\]

右侧是个幂和,上界可以根号分段,然后拉格朗日插值,左边用杜教筛求 \(\mu\) 区间和即可。

C Dream

solved by ghc,gjy


ghc,gjy’s solution

使任意两个数相加得0,乘法只需要满足每个数字都出现的条件即可。

D Find Integer

solved by sk


sk’s solution

费马大定理+构造勾股数

E GuGu Convolution

solved by gjy,sk


sk’s solution

赛中用了母函数+常系数线性齐次递推+矩阵快速幂,实际上只用二项式定理+快速幂就行了,答案是\((A+\sqrt{B})^n\)结果去掉整数项。

F Neko and Inu

unsolved

G Neko’s loop

solved by

H Search for Answer

upsolved by sk


sk’s solution

按照度数随便贪过去了,数据弱的一批

I Tree and Permutation

solved by

J YJJ’s Salesman

solved by sk


sk’s solution

树状数组求最值

Replay

ghc

gjy

sk