传说中的,鸭大计科鬼门关
题目大意
定义函数 $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
题目大意
维护三个长度为 $n$ 的序列 $A,B,C$,支持以下 7 种操作:(操作数为 $m$)
- $1\ l\ r$:对 $[l,r]$,$A_i \gets A_i+B_i$;
- $2\ l\ r$:对 $[l,r]$,$B_i \gets B_i+C_i$;
- $3\ l\ r$:对 $[l,r]$,$C_i \gets C_i+A_i$;
- $4\ l\ r\ v$:对 $[l,r]$,$A_i \gets A_i+v$;
- $5\ l\ r\ v$:对 $[l,r]$,$B_i \gets B_i \cdot v$;
- $6\ l\ r\ v$:对 $[l,r]$,$C_i \gets v$;
- $7\ l\ r$:求 $\sum_{i=l}^r A_i,\ \sum_{i=l}^r B_i,\ \sum_{i=l}^r C_i$,在模 $998244353$ 意义下。
$n,m \leq 2.5 \times 10^5,\ 0 \leq A_i,B_i,C_i < 998244353$
5s