#CW42. 排列检查(check)

排列检查(check)

题目背景

小 W 正在检查一批由小 Z 生成的排列。为了让检查结果稳定可复核,他使用一个固定的单调栈过程,并把所有询问的答案压缩成一个数。

题目描述

给定一个长度为 nn 的排列 aa。维护一个初始为空的递增单调栈 bb 和计数器 c=0c=0。依次处理 a1,a2,…,ana_1,a_2,\dots,a_n:

  1. 若 bb 为空,或栈顶小于 aia_i,将 aia_i 压入栈中;
  2. 否则弹出栈顶,并令 cc 加一,然后继续检查当前的 aia_i。

定义排列的逆序对数 inv\mathrm{inv} 为 ∑1≤i<j≤n[ai>aj]\sum_{1\le i<j\le n}[a_i>a_j]。

若处理结束时 cc 等于 inv\mathrm{inv},则称这个排列是合格的。

输入不会直接给出 aia_i。每个询问给出差分序列:规定 a0=0a_0=0,输入的第 ii 个数是 ai−ai−1a_i-a_{i-1}。保证还原出的 aa 是 1,2,…,n1,2,\dots,n 的排列。

输入格式

第一行一个正整数 tt,表示询问个数。

接下来 tt 行描述询问。每行先给出一个正整数 nn,随后给出 nn 个整数 did_i,其中 di=ai−ai−1d_i=a_i-a_{i-1},且 a0=0a_0=0。

对于全部数据,保证 1≤t≤21\le t\le 2,1≤n1\le n,所有询问的 nn 之和不超过本题所在子任务给出的限制;还原出的序列是 1,2,…,n1,2,\dots,n 的排列,并且 ∣di∣<100|d_i|<100。

输出格式

若第 ii 个排列合格,记 ansi=65537ans_i=65537;否则记 ansi=13579ans_i=13579。输出

$$\left(\sum_{i=1}^{t} 131^i \cdot ans_i\right) \bmod 993244853\text{。}$$

样例 1 输入

2
3 1 1 1
3 1 2 -1

样例 1 输出

140020951

样例 1 解释

两组差分分别还原为排列 (1,2,3)(1,2,3) 和 (1,3,2)(1,3,2)。前者没有逆序对,单调栈弹出次数为 00;后者有一个逆序对,单调栈恰好弹出一次,因此两组排列都合格。代入题目中的压缩公式得到 140020951140020951。

样例 2 输入

2
3 3 -2 1
3 3 -2 1

样例 2 输出

234808068

样例 3 输入

2
3 1 1 1
3 3 -2 1

样例 3 输出

241614566

样例 4 输入

2
3 3 -2 1
3 1 1 1

样例 4 输出

133214453

样例 5 输入

1
3 1 1 1

样例 5 输出

8585347

子任务

本题采用子任务捆绑计分。一个子任务中的所有测试点全部通过后,才能获得该子任务的分值;各子任务之间相互独立。

子任务 测试点 额外限制 分值
1 1∼31\sim 3 所有询问满足 n≤8n\le 8,且 ∑n≤16\sum n\le 16 10
2 4∼74\sim 7 所有询问满足 n≤1000n\le 1000,且 ∑n≤2000\sum n\le 2000 15
3 8∼118\sim 11 所有询问满足 n≤105n\le 10^5,且 ∑n≤2×105\sum n\le 2\times 10^5 20
4 12∼1512\sim 15 所有询问满足 n≤5×105n\le 5\times 10^5,且 ∑n≤106\sum n\le 10^6 25
5 16∼2016\sim 20 无额外限制,∑n≤2×106\sum n\le 2\times 10^6 30

数据范围

除特别说明外,所有数据满足 1≤t≤21\le t\le 2、1≤n1\le n、∣ai−ai−1∣<100|a_i-a_{i-1}|<100,并且还原出的 aa 是 1,2,…,n1,2,\dots,n 的排列。所有测试点中 ∑n≤2×106\sum n\le 2\times 10^6。