NOIP模拟题 DAY1

第一题 余数

【题目描述】　
　　给你两个整数$n,m$，求$(\sum_{i=1}^m{n~mod~i})~mod~{10}^9+7$。
【输入格式】
　　一行两个整数$n,m$。
【输出格式】
　　一个整数：答案。
【样例输入】

3 4 

【样例输出】

4

【样例解释】
　　$(3~mod~1)+(3~mod~2)+(3~mod~3)+(3~mod~4)=0+1+0+3=4$
【数据范围】
　　对于$10\%$的数据：$n,m\leq10$；
　　对于$30\%$的数据：$n,m\leq{10}^3$；
　　对于$50\%$的数据：$n,m\leq{10}^7$；
　　存在$20\%$的数据：$n<m$；
　　对于$100\%$的数据：$1\leq n,m\leq{10}^{13}$；

第二题 糖果

【题目描述】
　　ZJT有$n$个糖果，第i个糖果的甜蜜值为$a_i$，价值为$b_i$。ZJT想吃掉不大于$\lfloor \frac{n}{2} \rfloor+1$个糖果，使得他吃掉的糖果的甜蜜值之和大于他所有糖果的甜蜜值之和的一半，他吃掉的糖果的价值之和大于所有糖果的价值之和的一半。
　　简单来说，就是有两个数列$a,b$，你要选出不大于$\lfloor \frac{n}{2} \rfloor+1$个整数$c_1,c_2,…c_k$，使得$2\sum_{i=1}^k{a_{c_i}}>\sum_{i=1}^n{a_i}, 2\sum_{i=1}^k{b_{c_i}} >\sum_{i=1}^n{b_i}$ 。
【输入格式】
　　第一行有一个整数$n$；
　　第二行有$n$个整数$a_i$；
　　第三行有$n$个整数$b_i$；
【输出格式】
　　若有解：
　　　　第一行输出一个整数$k$；
　　　　第二行输出$k$个整数$c_i$；
　　　　你可以按任何顺序输出你选的$k$个整数。
　　若无解：
　　　　输出$-1$；
【样例输入】

5
8 7 4 8 3
4 2 5 3 7

【样例输出】

3
1 4 5

【评分标准】
　　若你的答案正确，则该测试点得满分；
　　否则该测试点得$0$分。
【数据范围】

　　对于$100\%$的数据：$1\leq n\leq{10}^5,1\leq a_i,b_i\leq{10}^9$；

第三题 虫子

【题目描述】
　　有一棵有根树，共有n个点，根为1。除根之外每个点都有一个父亲，第$i$个点的父亲为$f_i$，保证这是一颗树。每个点上还有一块糖果，第i个点上的糖果的甜度为$a_i$。
　一共会发生$m$个事件：
　　$1~x~y$：把$f_x$改成$y$。如果$x$是$y$的祖先，就把$f_y$改成$x$。
　　$2~x~v$：把$a_x$改成$v$。
　　每个点上还住着很多只虫子。最开始和每个事件发生后，上帝会随机选择两个点（可以是同一个点），再在每个点上选择一只虫子，让他们开始爬行，直到相遇为止。爬行的规则如下：
　　　1.只能往父亲方向爬。即$x$只能爬向$f_x$。
　　　2.两只虫子爬行的距离之和必须最小。
　　上帝想知道，最开始和每个事件发生后，虫子相遇的点上糖果的甜度的期望是多少。
【输入格式】
　　第一行有一个整数：$n$；
　　第二行有$n-1$个整数，第$i$个整数是$f_{i+1}$
　　第三行有$n$个整数，第$i$个整数是$a_i$
　　第四行有一个整数：$m$；
　　接下来$m$行每行有一个事件。
【输出格式】
　　共$m+1$行，输出最开始和每个事件发生后，XXX的期望。
【样例输入】

　　5
　　1 2 2 1
　　1 2 3 4 5
　　5
　　1 3 4
　　1 4 5
　　2 2 3
　　1 5 2
　　1 1 4

【样例输出】

　　1.64
　　1.80
　　2.28
　　2.32
　　2.80
　　1.84

【数据范围】

　　对于$100\%$的数据：$1\leq n\leq{10}^5,0\leq m\leq{10}^5,1\leq f_i\leq n,0\leq a_i,v\leq {10}^6,1\leq x,y\leq n$
【样例解释】
　　初始时：

　　$\frac{1+1+1+1+1+1+2+2+2+1+1+2+3+2+1+1+2+2+4+1+1+1+1+1+5}{5^2}=\frac{41}{25}=1.64$
【评分标准】
　　若你的所有答案与所有标准答案的相对误差或绝对误差均小于$10^{-9}$，该测试点得满分，否则得$0$分。