已经刷不了几天了。。。
排个序就过了
手膜一下，你会发现魔改一下\(gcd\)就行了
刚开始猜了个乱搞，但觉得是假的没敢写，最后看了题解才知道真的是那样？
先说做法，就是如果\(k\)为偶数，就枚举每一个点作为根，然后把深度大于\(frac{k}{2}\)的都删掉；奇数的情况基本同理，就是枚举相邻的两个点，然后在两边分别删就行了
正确性感觉上是对的
看错题了，把最后一个条件理解为\(a\)和\(b\)的\(n\)个字母两两对应相等了。。。
考虑建一张图，两点之间有连边代表这两个位置的字母相同，那么合法的图必须是联通的。
然后随便画几个情况，按照各路神仙的说法，你会发现奇数特别没前途。事实上，只要有超过两个奇数就得输出不可能，证明如下：
设\(x\)为奇数的个数，那么把\(a\)中的边连完后会形成\(\frac{n-x}{2}+x\)个联通块，最少需要\(\frac{n-x}{2}+x\)边才能把他们联通，而\(b\)中最多可以提供\(\frac{n}{2}\)条边，由此我们可以推出，如果边数足够，有：
\[\frac{n-x}{2}+x-1\leqslant \frac{n}{2}\]
解得
\[x\leqslant 2\]
证毕
最后我们需要把\(b\)构造出来，考虑把奇数放到\(a\)的头尾，然后大力讨论一下怎么连边就行了
注意不能输出\(0\)
考虑那个二项式系数的组合意义：每次只能向上或向右走一格，从\((-A_i,-B_i)\)走到\((A_j,B_j)\)的方案数。然后就是个普及组\(dp\)了
最后统计时要减去自己到自己的贡献然后除以\(2\)
P.S.这个转化似乎挺常用的
第一步的转化没有想到怎么办啊
考虑搞一个序列\(q\)，\(q[p[i]]=i\)，那么问题等价于使\(q\)的字典序最小，每次操作可以交换\(q\)中相邻的且差值大于等于\(k\)的两个元素
发现无论怎么交换，差值小于\(k\)的两个元素的先后顺序是不会变的，而且先后关系正确的序列一定合法。这样提示我们建个图并在其中连有向边代表先后关系，然后就变成一个拓扑排序的题了
但是这样建图的复杂度是\(O(nk)\)的，显然有一些边是冗余的，我们可以拿线段树优化一下，这样边的数量就变成\(O(n)\)级别的了
最后只要用小根堆搞一个字典序最小的拓扑序就行了
代码不长。。。
P.S.对于排列，建立权值到位置的双射似乎挺常用的
原文：https://www.cnblogs.com/dummyummy/p/11147170.html