题目大意
一个置换可以看成是有 $a_1$ 个长度为 $1$ 的环 + $a_2$ 个长度为 $2$ 的环 + …… + $a_n$ 个长度为 $n$ 的环,满足 $\sum_{i=1}^n i\cdot a_i=n$ 。
记 $f(a_1,a_2,\cdots,a_n)$ 表示各种环的数量分别为 $a_1,\cdots,a_n$、长度为 $n$ 的置换的数量,现给定 $n,p$($p$ 是质数),问有多少种不同的数列 $a_1,\cdots,a_n$,满足 $p \not|\ f(a_1,a_2,\cdots,a_n)$ 。
$n \leq 10^{18},\ \ 2 \leq p \leq 10^5$
多测,$T \leq 10^5$,2s
传说中的,鸭大计科鬼门关
题目大意
定义函数 $f(n)$ 表示对 $n$ 一直求数位和直至 $n$ 为个位数,即:
其中 $g(n)$ 表示 $n$ 的数位和。
现在有一个很大的 $n$,你要求 $f(n)$。
这个 $n$ 是根据四个参数 $a,b,m,k$ 生成的,首先生成 $k$ 个数 $a,a+b,a+2b,\cdots,a+(k-1)b$(都在 $\bmod~m$ 意义下),然后把它们从后往前拼起来,就是 $n$。比如,$a=42,b=42,m=2018,k=18$,会生成 $n=7567146726305885465044624203783362942522101681268442$。
$0 \leq a,b \leq 10^9,\ 2 \leq m \leq 10^9+7,\ 1 \leq k \leq 10^9$
多测,$T \leq 10^4$
正儿八经的用析合树本身的题没见着,析合树形态计数倒是一大堆。。。
题目大意
给定一棵 $n$ 个点的 AVL 树(点权恰好为 $1$ 到 $n$),你需要选择其中的 $k$ 个点,满足:
- 如果要选一个点,那么它的祖先也必须选。也就是选出来的 $k$ 个点会组成一棵新的树。
- 这棵新的树也必须是 AVL 树。
(放个传送门里面有图片可以看看例子
每种选法可以表示为一个长度为 $n$ 的 01 串(表示每个点选或不选),你需要求出字典序最大的方案。
$1 \leq k \leq n \leq 5 \times 10^5$
4s,256MB
题目大意
有 $k$ 棵树,每棵树有 $n$ 个点,对于所有的点对 $(s,t)$($1 \leq s,t \leq n$),求出有多少个点在每棵树的 $s$ 到 $t$ 的链上都存在。
(以防表述不清,给一下传送门
$n,k \leq 500$
2s