「ASF Mar19 D10」逆序对【平衡树】

Time Limit: 2 Sec Memory Limit: 1024 MB

Description

给定一个排列 pp,称其逆序对个数为满足 pi>pj,p_i > p_j, i<ji < j(i,j)(i, j) 对数。

排列上的一个区间 [l,r][l, r] 会发生循环移位 kk 次的变化,即对于新的排列 pp' 有:

px=p(xl+k) mod (rl+1)+l(lxr)p'_x = p_{(x - l + k) \text{ mod } (r - l + 1) + l} \quad (l \leqslant x \leqslant r)

对于每次修改后得到的排列 p0p_0,求出整个排列循环移位 kk 次后的所有排列 pkp_k 中,逆序对个数最小的排列是哪一个。输出使得逆序对数最少的最小的 kk 即可。

Input

第一行两个整数 n,qn, q,表示排列的长度和询问的次数。

接下来一行 nn 个数,表示初始时的排列。

接下来 qq 行,每行三个数 l,r,kl, r, k,表示这次的操作。

Output

输出 qq 行,第 ii 行输出一个数,表示前 ii 次操作后的答案。

查看更多

「ASF Mar19 D8」染色【DP + 概率与期望】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

有一棵 nn 个点的树,一开始树上每个点都是白色的。

每次从 n(n+1)2\dfrac{n(n + 1)}{2} 条路径中等概率随机选择一条,并把这条路径上的点全部染黑。

求期望多少次后所有的点都被染黑。答案对 998244353998244353 取模。

Input

第一行一个整数 n​。

接下来 n1n - 1 行,每行两个整数 u,vu, v,表示点 uu 和点 vv 之间有边。

Output

输出一行一个整数,表示答案。

查看更多

「ASF Mar19 D7」麻将【搜索】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

麻将中共有 3434 种牌,每种牌各 44 张。分别是一万到九万 ((万子))、一筒到九筒 ((筒子))、一索到九索 ((索子))33 类数牌,以及东西南北白发中这 77 种字牌。

接下来用 1m\text{1m}9m\text{9m} 表示一万到九万,类似地用 p\text{p} 表示筒子,s\text{s} 表示索子,77 种字牌则用 1z\text{1z}7z\text{7z} 表示。

12m\text{12m} 表示 111m\text{1m}112m\text{2m}。用 1m22p\text{1m22p} 表示 111m\text{1m}222p\text{2p}

麻将中,必须要能划分成 44 个面子加 11 个雀头的 1414 张牌才能和牌 ((不考虑国士无双和七对子))

面子分为顺子和刻子。顺子是 33 张数字连续的同类数牌,如 345m,\text{345m}, 789s\text{789s} 等。字牌不能形成顺子。刻子是 33 张相同的牌,如 222p,\text{222p,} 777z\text{777z} 等。顺子和刻子都是面子。

雀头是 22 张相同的牌,如 66s,\text{66s,} 11z\text{11z} 等。

现在你有 1414 张牌,你要求出至少再摸几张牌才能和牌。

Input

第一行一个整数 TT,表示询问次数。

接下来 TT 行,每行按题目描述中的格式输入 1414 张牌。

Output

输出 TT 行,每行一个数,依次表示 TT 次询问的答案。

查看更多

「ASF Mar19 D5」水晶矿石【容斥原理 + 状压 DP】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

比特镇的矿山出产 nn 种不同的水晶矿石,晶莹剔透、光彩夺目。

在世界上一共发现了 mm 种元素,每种矿石都对应着某种元素,不同的矿石可能会对应同一种元素,但是每种矿石不会对应多个元素。

经过测量,第 ii 种水晶矿石的特征值为 wiw_i。研究表明,如果三种矿石的特征值分别可以表示成 k,2k,3kk, 2k, 3k,则它们不会对应着同一种元素。换句话说,假设这三种矿石分别为 A,B,CA, B, C,那么它们不能都对应第 11 种元素,但是 A,BA, B 都对应第 11 种元素,CC 对应第 22 种元素是合法的。

请写一个程序,计算所有可能的对应方式的数量。

Input

第一行包含两个整数 n,mn, m,表示矿石和元素的种类数。

第二行包含 nn 个互不相同的整数 w1,w2,,wnw_1, w_2, \cdots, w_n,表示每种矿石的特征值。

Output

输出一行一个整数,表示合法的方案数,对 10000000071\, 000\, 000\, 007 (=109+7)(= 10^9 + 7) 取模。

查看更多

「ASF Mar19 D4」安全【DP + 树状数组】

Time Limit: 2 Sec Memory Limit: 512 MB

Description

坦克新兵们要去训练场训练了。训练场可以看作一个二维平面,其中有 nn 堵墙,每堵墙可以看作一条竖直线段。保证线段两两不交 ((包括线段的顶点))

一辆坦克可以看作平面上的一个点,该点不能和墙相交。坦克兵可以对坦克进行两种操作:

  • 一种是移动,只能是水平移动,即保持 yy 坐标不变;
  • 一种是开炮,只能是竖直开炮,炮弹可以视作一条平行 yy 轴的向上的射线。

你需要给每辆坦克安排一个初始坐标,使得无论每个坦克兵如何操作,都能确保安全 ((即不会被其他坦克击中))。假设每个坦克兵操作合法,不会开着坦克撞到墙上。

你得知 nn 堵墙中可能存在至多一堵危墙,可能在训练时倒塌,此时可视作该墙不复存在。

请你输出在这种情况下,确保安全的前提下最多能安排几辆坦克。

Input

第一行包含一个整数 nn

接下来 nn 行,第 ii 行三个整数 xi,ai,bix_i, a_i, b_i (0xi109,(0 \leqslant x_i \leqslant 10^9, 0ai<bi109)0 \leqslant a_i < b_i \leqslant 10^9),表示第 ii 堵墙为连接 (xi,ai)(x_i, a_i)(xi,bi)(x_i, b_i) 的线段。

Output

输出一行一个整数,表示所求的最大值。

查看更多