Official Editorial: https://img.atcoder.jp/agc043/editorial.pdf

https://blog.csdn.net/zxyoi_dreamer/article/details/105078186

The video analysis, test data and solutions has been uploaded. (Only visible for users with FTP access)

各地市信息学组织单位及有关中小学：

为了给学有余力、爱好信息学的中小学生提供继续学习、相互交流和再提高的机会，培养信息学优秀后备人才，并争取在今后的全国青少年信息学奥赛（竞赛、联赛等）中取得更好的成绩，山东省信息学奥赛委员会定于2021年7月15日—7月22日在山东外国语职业技术大学举办山东省信息学奥林匹克夏令营。现将有关事项通知如下：

一、参加对象

参加夏令营的学生均需是身体健康、好学上进、纪律性强的优秀中学生（高中和初中）或高年级小学生，学生可根据各自情况自愿报名参加，并选择适合自己学习的班级。

1. 参加过往年信息学有关赛事（如CSP2020,NOIP2020），并希望进一步提高的中小学生。省队队员（ABECD类 ）必须参加省队集训。
2. 爱好计算机，渴望学习信息学，学有余力，希望学习编程并得到信息学锻炼的优秀中小学生。
3. 各地市信息学负责人和普通中小学的信息学辅导老师。
4. 预计7月15（报到日）-20日（返程日）举办全国NOI指导教师培训班（和夏令营同时举办，可以提前做好准备），等全国确认安排后单独再通知。

二、夏令营时间

夏令营时间：2021年7月15日（周四）--7月22日（周四），其中：

• 7月15日（周四，13:00—19:00）报到；
• 7月16日--7月22日，共计7天培训（晚上安排讲座或者报告）；
• 7月22日下午4：30后（下午提前上课）可以返程。

三、学习内容与安排

营员有针对性地学习： C++语言编程、数据结构、常用算法、算法设计、典型例题分析、综合强化训练等。

根据营员现有学习基础和水平分为6个层次的班：语言基础班(100人)、语言提高班(100人)、数据结构基础班(200人)、数据结构提高班(200人)、高级算法班(60人)和集训班(40人)，具体要求见“附件一 分班安排表”。 另外，晚上安排金银牌高手讲坛与金牌之路、名校学生风采及专题讲座、金牌教练经验分享及专题报告，每个学生和老师都可以近距离听到金牌高手和金牌教练的报告。预计安排1场金牌之路报告，4场金银牌选手的专题报告，2个名校学生风采、2次金牌教练的经验分享报告。

四、报到和活动地点

活动和报到地点:山东外国语职业技术大学（原山东外国语职业学院）(地址:山东省日照市山海路99号)。山东省外国语职业技术大学是本科高校，学校占地1000多亩，环境非常优美、沿海气候，承办条件非常好，学生公寓四人间有空调、热水和独立卫生间。2019和2020年连续承办过山东省信息学夏令营、CSP-JS二轮认证考试和NOIP2020。

五、交通

各地营员自行乘车前往。如果是乘火车或汽车到达，可按以下公交方式乘车前往：

1. 日照高铁站/日照汽车站(高铁站/日照汽车站--技术大学17公里，可打出租车)：
   1. 步行约1.5公里左右，到达长沙路大同路乘坐17路，经过34站，到达山东外国语职业技术大学。
   2. 乘坐C106路，经过19站，到达会展中心，步行约20米，到达会展中心乘坐31路，经过16站，到达山东外国语职业技术大学。
2. 日照火车站（日照站--技术大学9.5公里,可打出租车）：
   1. 乘坐11路，经过24站，到达日照职业技术学院，向北步行约880米，到达山东外国语职业技术大学。
   2. 向西步行约1.0公里，到达荣安大厦站乘坐31路，经过19站，到达山东外国语职业技术大学。

六、营员食宿安排

所有营员(学生和教师)统一安排在承办学校餐厅就餐。学生营员统一安排在承办学校学生公寓住宿（4人1间，有空调、热水和卫生间，自带洗漱用品和换洗衣物）。教师或领队也统一安排住学校学生公寓（2人1间，有空调、热水和卫生间，每人提供一套洗漱用品）。夏令营期间实行全封闭式管理（学生和教师全部在学校食宿），按照防疫要求进行管理和安排。

七、培训费用

所有学生营员每人培训费用1400元（含保险费用）、食宿费1200元（含食宿费用、资源使用费和部分防疫费用），共计2600元。教师营员培训和住宿费用合计2200元（可以申请开发票回单位报销，如果需要住宾馆的，联系承办单位联系人），如果指导教师参加全国NOI指导教师培训，单独再通知，教师营员培训和住宿费用（时间重复）可能调整。

大家好，我是钱易

我来自嵊州市城南学六（2）班

我今年十二岁

奔跑吧钱易

奔跑吧钱易

奔跑吧钱易

奔跑吧钱易

我是个帅气的阳光男孩

我爱我的学校，我的六二班

我的同学们很团结，很快乐的学习和生活着

我是一个品学兼优的好孩子

课外也有很多业余爱好

我爱玩魔方

因为魔方中的数学内容丰富，生动有趣

我爱下象棋

它包含着很多人生的智慧和哲理

我爱跑步

因为它会让我更强壮

我爱游泳

因为我向往大海

我想畅游在鱼儿的部落里

看着海母公主在我身边翩翩起舞

我从小爱动脑

小学三年级起，我迷上了奥数

学校里认真听老师讲课

回家后自己暗暗的努力

奇迹发生了

2014年，我获得希望杯浙江赛区一等奖

2015年，我获得世少赛一等奖

并获得华罗庚金杯小高组三等奖

四年级起，我又迷上了信息技术

数学老师极力推荐我进入了信息技术班

从此，我的生活被0和1这两个神奇的数字包围

四年级学完了计算机基础知识

五年级掌握了各种顽皮的算法

打败了很多六年级的高手

获得了参加绍兴市信息技术比赛决赛的资格

不巧的是，信息技术比赛和华罗庚金杯赛决赛撞车了

两个比赛之间只有两个小时的间隔

我不仅需要同时备战两个比赛

而且比赛当天我必须在两个小时内从宁波赶回嵊州参赛

这对我这样一个晕车的孩子来说，放弃一个比赛是最明智的选择

但我最后选择了坚持

不仅顺利完赛

而且以五年级的身份战胜了很多六年级同学

获得了华杯赛小高组浙江赛区三等奖

同时，下午的信息技术比赛我也已92分的高分进入了决赛

接下来的时间自然是

PASCAL PASCAL PASCAL

算法、算法、算法

努力 努力 再努力

结果 \

当然 \

是一等奖

在这里我要衷心的感谢过老师，谢谢她这几个月的辛劳

通过这次比赛

我觉得我这个还算勤奋，但还可以再勤奋点的淘气男孩

应该是个有潜力的孩子

能在竞争的环境中接受挑战

锻炼自己，学习得更好，幸福地成长

task1 n=1

输出 $1$ 到 $n$ 中所有奇数的和即可

task2 m<=100

暴搜

task3 m<=10^6,n<=10

设 $f(i)$ 表示权值乘积为 $i$ 的树的权值和

容易看出 $f(i)$ 为积性函数

因此只需要求出所有 $f(p^k)$ 的值

考虑这样一个问题:对树上每个点分配一个非负整数权值 $a_i$ ，使得 $\sum a_i=k$

求对于每个 $v$ ,树上所有路径上的权值 $min$ 的和为 $v$ 的方案数

容易发现只要求出这个问题，就可以求出 $f(p^k)$

首先考虑 $v$ 的上界

设 $g_{u,i}=[a_u>=i]$ ,则 $\sum_u \sum_{i=1}^k g_{u,i} =k$

有 $v=\sum_{S\ is \ a \ path \ in \ T} min_{u\in S}a_u$

$v=\sum_{S\ is \ a \ path \ in \ T} \sum_{i=1}^k \prod_{u\in S}g_{u,i}$

$v=\sum_{i=1}^k \sum_{S\ is \ a \ path \ in \ T} \prod_{u\in S}g_{u,i}$

容易证明，对于 $n$ 个点的森林，不同路径数不超过 $n*(n-1)/2$

因此 $v\leq \sum_{i=1}^k (\sum_ug_{u,i})*(\sum_ug_{u,i}-1)/2$

因为 $\sum_{i=1}^k\sum_u g_{u,i} =k$ ，可以得到 $v\leq k*(k-1)/2$

对于这一个task， $k\leq 12$ ,可以暴搜所有 $a_i$ ，然后线性筛 $f$ 即可

task4 m<=10^10,n<=10

对于 $n\leq10,k\leq20$ 的部分，暴搜可以较快的得到答案

注意到 $f(p)=[p>2]p$ ，$f(p^k)$ 已经求出，因此可以 min_25 筛解决问题

task5 m<=10^6,n<=50

考虑一个 $dp$ : $dp_{i,j,v,S}$ 表示 $i$ 的子树内，已经分配了 $j$ 的权值， $i$ 子树内的路径点权 $min$ 和为 $v$，当前 $i$ 子树内的每一个点到 $i$ 路径上的点权 $min$ 组成的可重集为 $S$ ，当前的方案数

首先可以无视 $S$ 中的 $0$ ,对于一个点 $u$ ,$u$ 到 $i$ 路径上的点权 $min\leq a_u$

因此 $S$ 中元素和小于等于 $j$ ,因此不同的 $S$ 最多有 $\sum_{i=0}^k partition(k)$ 个

在 $k\leq 12$ 时有 $272$ 个， $k\leq 18$ 时有 $1597$ 个， $k\leq 20$ 时有 $2714$ 个

考虑将 $v$ 和 $S$ 压成一个状态，发现在随机下这个状态不会太多， $k=20$ 大概在 $17000$ 以下(我不会证不随机时的极限)，在 $k\leq 12$ 时更小，可以计算一个 $hash$ 值，开map统计

$dp$ 转移时，枚举 $i$ 位置的权值 $a_i$ ,然后依次枚举每个子树内的权值和和状态，暴力合并状态

这样在随机下效率很好，可以通过

task6 m<=10^9,n<=50

task7 m<=10^9,n<=100

task8 m<=10^10,n<=50

上述算法不同常数的实现

task9 m<=10^9,n<=50

仍然是上一个算法，考虑如何加速状态合并和如何去掉map

以下是一种方式:

我们用一个数 $v$ 来表示 $S$ ，$v$ 的计算方式如下:

如果 $S$ 中有一个 $1$ ,$v$ 值等于 $S$ 删去这个 $1$ 后的值乘 $2$ 加 $1$

否则, $v$ 值等于 $S$ 中所有元素减 $1$ 后的集合的值乘 $2$

可以发现这样一个 $v$ 对应的 $S$ 唯一，且这样的 $v$ 不会大于 $2^{S元素和}$

对于两个 $v$ ，可以较快的合并，具体参考std

因为 $v$ 不大，所以可以用数组实现 $v$ 和 $1 - 2714$ 的对应

然后考虑状态第一维不超过 $190$ ,第二维不超过 $2714$ ，因此可以用另外一个数组实现对应，这样就去掉了map

加上上面的优化即可通过此题