数数
题意
ame 是一个可爱的女孩子，她想要你帮她数数。
给定 $n$ 个正整数 $a_n$ 和 $T$ 组询问，第 $i$ 次询问给定 $p_i$，询问从第 $p_i+1$ 个数往后第一个不是前 $p_i$ 个数的倍数的数是多少。
如果给定的 $n$ 个数中不存在这样的数，则输出 $-1$。
对于所有数据，$1\le n,T\leq 2\times10^5$，$1 \le a_i\leq10^7$。
输入格式
输入共 $3$ 行。
第 $1$ 行输入 $2$ 个数 $n,T$。
第 $2$ 行输入 $n$ 个正整数，表示 $a_1,a_2,a_3,\ldots ,a_n$
第 $3$ 行输入 $T$ 个正整数，表示 $p_1,p_2,p_3,\ldots ,p_n$
输出格式
输出共 $1$ 行 $T$ 个整数。第 $i$ 个整数表示第 $i$ 次询问的答案。
数据范围
对于 $10\%$ 的数据，$n,T \leq 100$。
对于 $30\%$ 的数据，$n,T\leq 1000$。
对于另外 $20\%$ 的数据，$T=1$。
对于所有数据，$1\le n,T\leq 2\times10^5$，$1\le a_i\leq10^7$，$1 \le p_i \le n$。
样例输入1
5 5
5 5 2 3 4
1 2 3 4 5样例输出1
2 2 3 -1 -1样例输入2
8 8
9 4 2 4 7 3 8 1
8 2 3 1 4 5 7 6样例输出2
-1 2 7 4 7 3 1 1最长上升子树链
题目描述
蒜头君有两棵 $n$ 个节点的树， 这是第一棵。
这是一颗以 $1$ 为根的树， 树上每个点有一个权值 $v_i$, 现在蒜头君想问问聪明的你，这棵树的最长上升子树链为多少。
何为上升子树链？
答曰：就是求一个由点编号构成的序列 $a[1\dots m]$ ,要求满足：
-
存在一个 $k$ , $1 \le k \le m$ , 满足在 $2 \le i \le k$ 中，$a[i-1]$ 在以 $a[i]$ 为根的子树中，在 $k+1 \leq i \leq m-1$ 中，$a[i+1]$ 在以 $a[i]$ 为根的子树中。
-
$2 \le i \le m$ 中，$v[a[i]] > v[a[i – 1]]$
输入格式
第一行一个整数 $n$。
接下来 $n$ 行，每行两个整数 $v_i, \mathrm{fa}_i$， 表示第 $i$ 个点的权设置和父亲节点。 我们假定 $1$ 的根节点为 $0$。
输出格式
一个整数，表示答案。
数据范围
- $\texttt{Subtask 1(30 pts)：}\mathrm{fa}_i=i-1$；
- $\texttt{Subtask 2(30 pts)：}1 \le\ n\le 10^3$；
- $\texttt{Subtask 3(40 pts)：}$无特殊限制。
对于 $100\%$ 的数据，满足 $1 \le n \le 10^5, 0 \le v_i \le 10^9$
样例输入1
4
10 0
5 1
5 1
11 3样例输出1
3样例输入2
10
1 0
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9样例输出2
10计算
题目描述
ame 是一个可爱的女孩子，她想要你帮她计算一个式子。
给定 $T$ 组询问，每组询问给定 $n,a,b$，求
$$ \sum{i=1}^n\sum{j=1}^n \left[\left(a+\sqrt{b}\right)^i\right]\left[\left(a+\sqrt{b}\right)^j\right] $$
答案对 $998244353$ 取模，其中 $[x]$ 为小于等于 $x$ 的最大整数。
对于所有数据，$1 \le T\leq 10^5$，$1 \le n \le 10^8, 0\le a,b\leq 10^8$，$(a-1)^2\leq b\leq a^2$。
输入格式
输入共 $T+1$ 行。
第 $1$ 行输入 $1$ 个正整数 $T$。
接下来共 $T$ 行，每行输入 $3$ 个正整数 $n,a,b$，表示一次询问。
输出格式
输出共 $T$ 行，每行输出 $1$ 个整数，表示答案对 $998244353$ 取模的结果。
数据范围
对于前 $10\%$ 的数据，$T=1$，$n\leq 5$。
对于另外 $10\%$ 的数据，$b=a^2$。
对于前 $40\%$ 的数据，$T\leq 100$，$n\leq 100$。
对于前 $70\%$ 的数据，$T\leq 100$，$n\leq 10^5$。
对于另外 $10\%$ 的数据，$T\leq 100$。
对于所有数据，$1 \le T\leq 10^5$，$1 \le n \le 10^8, 0\le a,b\leq 10^8$，$(a-1)^2\leq b\leq a^2$。
样例输入
5
1 3 5
2 3 5
5 3 5
114514 30 907
1919810 10000 99999999样例输出
25
1024
23629321
146399689
702663296Limbo
题目背景
题目描述
APJifengc 想要练习它的动态视力，所以他开始练习打 Limbo 的结尾段。
这一段的规则是这样的：有 $n$ 个钥匙形成一个环，这 $n$ 个钥匙中有 $1$ 个是真钥匙，剩下的 $n-1$ 个均为假钥匙。这些钥匙会进行 $m$ 次打乱，打乱的过程是每次等概率随机一个长度为 $n$ 的排列 ${p_i}$，然后将第 $i$ 个钥匙移动到 $p_i$ 的位置。打乱完 $m$ 次后，APJifengc 需要选出正确的钥匙。如果选择错误，那么 APJifengc 就需要重新开始。
但是，APJifengc 的动态视力并没有训练到能够 $100\%$ 看清每次打乱的地步。具体来说，每进行一次打乱，APJifengc 有 $\frac{1}{p}$ 的概率看不清钥匙是怎么打乱的。那么，此时 APJifengc 有两种选择，一种是直接重开，另一种是等到 $m$ 次打乱结束后，凭运气猜一个钥匙，如果最后没有猜中，那么只能重开。
我们规定钥匙每旋转一轮就会经过 $1$ 的单位时间，重开与最后的选择钥匙不消耗时间。APJifengc 想要知道，期望经过多少单位时间后，他能够选中正确的钥匙。
由于 APJifengc 是个很精细的人，他想要知道极其精确的答案，但他同时也需要一个粗略的估计，所以你需要同时输出答案的实数值与模 $998244353$ 意义下的值。关于期望值在模 $998244353$ 意义下的定义，请见题目最后面的补充。
当然，如果你求不出精确值，APJifengc 也不会为难你，如果你只答对了实数值，那么你将获得本题 $60\%$ 的分数。
输入格式
输入包括一行四个整数 $t, n, m, p$。其中 $t = 0$ 表示只需要输出实数值，$t = 1$ 表示除了实数值以外，还需要输出精确值。$n, m, p$ 的含义见题目描述。
输出格式
对于 $t = 0$，输出包括一行，为一个实数。如果你的答案与正确答案的绝对或相对误差不超过 $10^{-6}$，即判定为正确。
对于 $t = 1$，额外输出一行，为一个整数，表示期望时间在模 $998244353$ 意义下的答案。
数据范围
测试点编号
| 测试点编号 | n,m≤ | 特殊性质 |
|---|---|---|
| 1,2,3 | 10 | t=0 |
| 4,5 | 10 | t=1 |
| 6,7,8,9,10,11,12,13,14 | 102 | t=0 |
| 15,16,17,18,19,20 | 102 | t=1 |
| 21,22,23 | 105 | t=0 |
| 24,25 | 105 | t=1 |
对于所有的数据，满足 $1 \le n, m \le 10^5, 2 \le p \le 5 \times 10^5$。
在合理的范围内，选手无需担心浮点数误差带来的精度问题。
补充
期望值在模意义下的定义：
假设答案期望值为 $\frac{a}{b}$，那么你需要输出一个整数 $x$，满足 $x b \equiv a \pmod {998244353}$。
样例输入1
0 2 2 2样例输出1
3.2样例解释1
此时的最优策略为如果没有看清，就直接等最后猜钥匙。
- 有 $\frac{1}{4}$ 的概率可以准确知道真钥匙的位置；
- 有 $\frac{3}{4}$ 的概率不能准确知道真钥匙的位置；
- 其中，有 $\frac{1}{2}$ 的概率能够猜中，$\frac{1}{2}$ 的概率不能猜中。
综上，经过一轮后能够选中真钥匙的概率为 $\frac{1}{4} + \frac{3}{4} \times \frac{1}{2} = \frac{5}{8}$，不能选中真钥匙的概率为 $\frac{3}{4} \times \frac{1}{2} = \frac{3}{8}$。那么期望时间为 $2 + \frac{3}{8}\left(2 + \frac{3}{8}\left(2 + \cdots\right)\right) = \frac{16}{5}$。
虽然在本样例中 $t = 0$，对于精确值没有要求，这里给出其精确值在模意义下的值，为 $598946615$。
样例输入2
1 4 6 15样例输出2
7.491314735096
315581326样例输入3
1 82 97 114样例输出3
153.933361371106
422268238