Count
题面
考场
主攻它！
首先因为它要求所有数不是 $m$ 的倍数，所以首先考虑容斥一下把 $m$ 扣掉。
大概的式子是这样的：
$\Large C_{n - 1}^{m - 1}-\sum\limits_{k=1}^{\frac {n}{m}}C_{n-km-1}^{m-1}-\sum\limits_{k=2}^{\frac {n}{m}}C_{n-km-1}^{m-2}-…$
我一开始想的是把下面一样的合并一下求，但是没有发现简洁公式。而且这个式子本来就是 $\large\frac{n}{m}$ 项的， $n$ 那么大它项数就直接炸了。
所以换一个思路，考虑他们对 $m$ 的余数。因为不被整除，所以原式可以直接表示成 $\sum a_i\equiv A\mod m$ 。所以每一个 $a_i$ 可以转化成对 $m$ 的余数和商两部分，商部分因为没有任何限制，所以可以直接挡板法求，余数部分相当于若干个 $\in[1,m-1]$ 的整数相加与 $n$ 模 $m$ 同余。同样，我们把 $n$ 也分成被 $m$ 组成的部分和被余数组成的部分，因为余数有范围，所以 $n$ 被余数组成的部分 $N’\in [k,k(m-1)]$ 。这个东西规模就从 $10^{18}$ 缩小成 $km$ 了。那我们来看怎么求这些余数部分。
首先是同余，所以 $N’$ 的取值也是以 $m$ 为间隔的，也就是我们可以枚举这个和，复杂度是 $k$ 的，然后还是可以挡板，但是有 $[1,~m -1]$ 的限制。容斥一下？有点麻烦先看看其他的吧。（不麻烦啊这就是正解！！！）
当时我开始想能不能用类似背包的东西递推一下。就是 $N’k$ 的，也就是 $mk^2$ 的。写完之后发现更新的那重可以去掉改成前缀和减，所以单个 $N’$ 的求值部分复杂度就降到 $mk$ 了，总复杂度就是 $mk^2.$
可以过 $70pt.$ 了！那这个还能优化吗。？可能真的是还可以的，但是时间已经差不多了。写了个对拍发现过了。
出分：$30pt…$ ？？我过了拍还挂分了？然后发现怎么都调不对。
结果最后我写的正解的代码跟他拍还是过了，但是还是WA了。？原因后面会说。。orz…
正解
容斥
真不难。。就是我上面说的容斥，先不考虑限制，然后减去一个超过了限制的结果，再加上两个超过了等等等。
当时真的就差实现的一步了。。至于实现就是超过限制的时候把超过的那 $m-1$ 减掉在求一个挡板。
然后就是它和前面的 $70$ 暴力过了拍但是 $WA$ 了的情况。。
经过长久的调试，我发现是再求组合数的地方爆了 $ll…$ 因为那是要求 $m$ 的倍数部分，所以是 $\large\frac{n}{m}+k-1$ 所以超级大，然后没取模直接成了 $ret…$ 就炸了。。关键是爆成负数我都不知道因为后面把负数取回来了。。
然后就 $A$ 了。应该不算道难题吧。。
$code:$ https://paste.ubuntu.com/p/dJRMVsjtkW/
生成函数。？
老师说是道板子。。但是没学。。咕。（好像说代码和容斥是一样的。？）
Pj
普及组？你在逗我。。
题面
考场
暴力滚了。
出分： $0pt.~~CE$ 了。。我随机数的 $ctime$ 头文件没打有尖括号。。
正解
好像也不算难吧。
首先题目把 $x$ 给你了，就分解质因数，因为质因数之间是独立的。（鬼知道啊。。）
然后发现每个数的质因数指数不超过 $2.$ 然后考虑递推，分别看 $1,~2$ 两种情况。
指数是 $1$ 的时候可以发现就是删除最后一列上的 $1$ 所在位置以及它所在的行，那么一共有 $n$ 个位置，所以就是 $f_i=if_{i-1}.$
指数为二的时候有两种情况，就是一个 $2$ 和两个 $1.$
一个二的时候可以类似上面转移，但是两个一就需要再考虑了。
考虑最后一列的 $i,j$ 有两个 $1.$ 第 $i,j$ 行的另一个 $1$ 在或者不在同列。首先要选两个 $1$ 在那就是 $\large C_i^2.$
- 不在同列的话我们考虑合并其中的两列（可以 $i$ 的到 $j$ 也可以反过来。），那么就变成了两个 $1$ 在一列上。这个就是 $\large 2C_i^2f_{i-1}.$
- 在同列的话我们首先去掉 $j$ 行和最后一列，然后在 $i$ 行另一个 $1$ 的位置变成 $2.$ 这个 $2$ 则考虑上面 一个 $2$ 的处理方法，那么同列情况的总数就是 $\large (i-1)C_i^2f_{i-2}.$ 注意因为上面一种情况我们算过这个一次了，所以要把它减掉。
这样就有总的转移式：
$\Large f_i=if_{i-1}+2C_i^2f_{i-1}-(i-1)C_i^2f_{i-2}$
这是对于每一个质因数的，总体而言呢？首先对于他们本身是可以加偶数个负号的，这个可以除了最后一行一列任意加，最后一行一列调整一下乘积即可，就是要乘上 $\large2^{(n-1)^2}.$ 然后乘上每一个质因数的答案即可。
然后线性递推出来记一下有几个 $1$ 几个 $2$ ，快速幂一下回答询问就好。
总复杂度 $O(n+q\log n).$ （$\log$ 在快速幂。）
$code:$ https://paste.ubuntu.com/p/fCnZ6myWHn/
Tg
考场
暴力滚了。但是还是手玩了几组样例，觉得那个序列挺有意思的，但是没时间了。
出分：$3pt.$ 这个点没有询问。。
正解
原来的那个最大下降子序列长度为 $2$ 的排列可以等价于一个前缀最大值序列。
前缀最大值序列是什么？就是每个位置记这个位置前缀的最大值。
为什么呢？对于一个前缀最大值序列，我们考虑改变了最大值的点，称为关键点，那么除去关键点之外的数字，它们必须是从小到大，并严格依次插入到空隙之中的。不然考虑有两个关键点 $i,j$ 中间有两个数 $x,y$ 不是关键点，但是 $x>y,p_x<p_y$ ，那么就会出现一个下降子序列 $i>x>y$ 长度大于 $2$ 了。（$i>x$ 是因为它现在在两个关键点之间，所以 $i$ 在区间 $[i,j)$ 里面是最大值。）就矛盾了，就证明了原命题。
至于出题人怎么想到这样转换就不得而知了。
然后询问呢？寻询问是给出 $x,~y$ 让 $a_x=y.$ 那么两种情况：
$x\leq y:$ $y$ 一定在关键点上，不然前面会有一个比它大的点，而前面只有 $x-2$ 位，却要填上 $y-1$ 个数由抽屉原理可知一定有一个比 $y$ 小的数在 $y$ 后面，那就有一个长度大于 $2$ 的下降子序列了。矛盾。
$x > y:$ 把整个序列反转过来就是上面的情况了。
他是关键点的话怎么求呢？
考虑前缀最大值序列是什么。一个这样的序列可以看做是在一个坐标轴上，从 $(0,0)$ 走到 $(n,n)$ ，每次只能向上或者向右走，并且不能超过直线 $y=x$ 的方案数。（横坐标是 $i$，纵坐标是前缀 $\max.$）这个应该比较好理解。
那么现在就相当于有一个必经点，那答案就可以直接用组合数求了：
$\Large Ans=(C_{(x-1)+(y-1)}^{x-1}-C_{(x-1)+(y-1)}^{x})\times (C_{(n-x+n-y)}^{n -x}-C_{(n-x+n-y)}^{n -x - 1})$
（上面要 $+1$ 是因为要手动过直线 $y=x$）
预处理阶乘快速幂求即可。时间复杂度同样 $O(n+q\log n).$