9
T1 刷怪塔
现在我们证明取 x=0x=0x=0 总是最优的。令最高层刷怪平台为 t=n−xt=n-xt=n−x，考虑通过接收平台满足目标的平台个数，即满足 i≤ti\le ti≤t 且 pi>tp_i>tpi >t 的 iii 的个数，由于 ppp 是一个排列，这个数量一定等于 pi≤t<ip_i\le t<ipi ≤t<i 的 iii 的个数，因此将 xxx 改为 000 后仍然满足 pi≤ip_i\le ipi ≤i，原来合法的仍然合法，不会变得更劣。
因此问题等价于求有多少 iii 满足 pi≤ip_i\le ipi ≤i，直接维护即可，时间复杂度 O(n+q)O(n+q)O(n+q)。
T2 染色
先将 1∼n−11\sim n-11∼n−1 的所有奇数颜色排成 …,5,3,1,?,1,3,5,…\dots,5,3,1,\text{?},1,3,5,\dots…,5,3,1,?,1,3,5,… 的形式，再将 1∼n−11\sim n-11∼n−1 的所有偶数颜色排成 …,6,4,2,?,?,2,4,6,…\dots,6,4,2,\text{?},\text{?},2,4,6,\dots…,6,4,2,?,?,2,4,6,… 的形式，将两者并排放置可以得到：
…,5,3,1,X,1,3,5,…,6,4,2,Y,Z,2,4,6,…\dots,5,3,1,X,1,3,5,\dots,6,4,2,Y,Z,2,4,6,\dots …,5,3,1,X,1,3,5,…,6,4,2,Y,Z,2,4,6,…
此时还剩下 0,n,n0,n,n0,n,n 三个颜色要放在 X,Y,ZX,Y,ZX,Y,Z 的位置，而不难发现 XXX 与 ZZZ 下标差恰好是 n+1n+1n+1，因此令 X=Z=n,Y=0X=Z=n,Y=0X=Z=n,Y=0 即可构造出一个符合条件的序列，时间复杂度 O(n)O(n)O(n)。
T3 数学题
当整式 PPP 的次数 nnn 固定时，所求即为 a0+a1+⋯+an=n+Sa_0+a_1+\cdots+a_n=n+Sa0 +a1 +⋯+an =n+S 的方案数，其中 a0,a1,…,an−1a_0,a_1,\dots,a_{n-1}a0 ,a1 ,…,an−1 为自然数，ana_nan 为正整数。这可以转化为 (a0+1)+(a1+1)+⋯+(an−1+1)+an=S(a_0+1)+(a_1+1)+\cdots+(a_{n-1}+1)+a_n=S(a0 +1)+(a1 +1)+⋯+(an−1 +1)+an =S，其中
a0+1,a1+1,…,an−1+1,ana_0+1,a_1+1,\dots,a_{n-1}+1,a_na0 +1,a1 +1,…,an−1 +1,an 均为正整数。由插板法可得方案数为 (S−1n)S-1\choose n(nS−1 )。
对于第一问，好的整式 PPP 的个数即为 (S−10)+(S−11)+⋯+(S−1S−1){S-1\choose 0}+{S-1\choose 1}+\cdots+{S-1\choose S-1}(0S−1 )+(1S−1 )+⋯+(S−1S−1 )，这等价于从 S−1S-1S−1 个物品中选出来任意多个物品的方案数，所以第一问的答案为 2S−12^{S-1}2S−1。
对于第二问，由于次数为 nnn 的好的多项式的个数为 (S−1n)S-1\choose n(nS−1 )，我们可以从小往大枚举 nnn，统计次数小于等于 nnn 的好的多项式个数之和，直到数量大于等于 kkk 时输出答案。由于当 (S−1n)S-1\choose n(nS−1 ) 随着 nnn 增大是指数级别增长的，复杂度可以接受。
实现时可能需要使用 __int128。
T4 探索
显然移动后 x+yx+yx+y 的奇偶性不会改变，所以每个方格都只会有一条对角线可能被经过。考虑对于所有 x+yx+yx+y 为偶数的点建图，在每一个方格能经过的对角线两点间连边。问题转化为在这个图上至少要删除几条边才存在一条从 (0,0)(0,0)(0,0) 到 (x,y)(x,y)(x,y) 的欧拉路径。
这张图上两个点间的最短路长度很容易计算：d(P,Q)=max(∣xP−xQ∣,∣yP−yQ∣)d(P,Q)=\max(|x_P-x_Q|,|y_P-y_Q|)d(P,Q)=max(∣xP −xQ ∣,∣yP −yQ ∣)。
而一张图存在欧拉路径的充要条件是起点和终点的度数为奇数，其余点度数均为偶数。不难发现这张图上度数可能为奇数的点只有四个：A(0,0),B(n,0),C(0,m),D(n,m)A(0,0),B(n,0),C(0,m),D(n,m)A(0,0),B(n,0),C(0,m),D(n,m)。具体地，按照 n,mn,mn,m 的奇偶性可以得到：
* n,mn,mn,m 都是奇数：奇度点是 A,DA,DA,D。
* nnn 是偶数，mmm 是奇数：奇度点是 A,BA,BA,B。
* nnn 是奇数，mmm 是偶数：奇度点是 A,CA,CA,C。
* n,mn,mn,m 都是偶数：奇度点是 A,B,C,DA,B,C,DA,B,C,D。
先考虑 n,mn,mn,m 中至少有一个是奇数时的做法。此时图中只有两个奇度点 AAA 和某一个角 ZZZ。若终点是 TTT，我们的目标就是删除一些边使得只有 A,TA,TA,T 的度数为奇数。不难发现这本质上相当于找到一条从 TTT 到 ZZZ 的最短路并删除，之后跑欧拉路径即可。
现在考虑 n,mn,mn,m 均是偶数的做法。类似地，我们要将 T,B,C,DT,B,C,DT,B,C,D 四个点分成两对，删去这两条最短路。可以证明，存在一种选这两条最短路的方案使得这两条最短路不重合。枚举配对方案，找到答案最小的一组即可。
注意上述讨论中没有考虑 T=A,B,C,DT=A,B,C,DT=A,B,C,D 的情况，实现时需要精细讨论。
时间复杂度 O(nm)O(nm)O(nm)。
有帮助，赞一个