C - Triangular Relationship
如果 \(K\) 是奇数，那么一定有 \(K\mid a,K\mid b,K\mid c\)，所以答案为 \(\lfloor\frac{N}{K}\rfloor^3\)。
如果 \(K\) 是偶数，还有可能 \(a,b,c\equiv \frac{K}{2}\pmod K\)，所以在奇数的基础上还要加上 \(\left(\lfloor\frac{N-\frac{K}{2}}{K}\rfloor+1\right)^3\)，注意如果 \(N<\frac{K}{2}\) 时不能加上。
D - All Your Paths are Different Lengths
先考虑 \(L=2^k\) 怎么做：只需要把 \(1-k+1\) 的点排成一排，\(i\) 和 \(i+1\) 的点分别连权值为 \(0\) 和 \(2^{i-1}\) 的两条边就可以了。
然后我们考虑 \(L\not=2^k\) 的情况，首先设 \(2^{mx}\leqslant L<2^{mx+1}\)，那么我们先构造一个如上的长为 \(mx+1\) 的链，然后我们从高到低遍历 \(L\) 的二进制，同时维护把比当前位更低（包括当前位）的位都置为 \(0\) 后 \(L\) 的值 \(now\)，如果 \(2^k(k\not=mx)\) 这一位是 \(1\)，则从 \(k+1\) 向 \(mx+1\) 连一条权值为 \(now\) 的边。
不难发现这样的构造方式是对的。
E - Stop. Otherwise...
我们考虑现在求 \(y\) 的答案。
那么如果 \(i\) 出现，则 \(y-i\) 就不能出现了，这样，我们可以把若干的两个和为 \(y\) 的权值一起考虑；如果 \(y\) 为偶数，则 \(\dfrac{y}{2}\) 只能出现一次； 剩下的数没有要求。
我们考虑以上三种情况的 OGF：
对于两个和为 \(y\) 的权值 \(a,b\)，当至少出现一次时，一定只能全是 \(a\) 或全是 \(b\)，所以其 OGF 为 \[ 1+2x+2x^2+2x^3+\dots=(1+x)(1+x+x^2+\dots)=\frac{1+x}{1-x} \] 对于 \(\dfrac{y}{2}\)，其只能出现 \(0\) 或 \(1\) 次，所以其 OGF 为 \(1+x\)。
对于剩下的没有要求的数，可以选任意个，所以其 OGF 为 \[ 1+x+x^2+x^3+\dots=\frac{1}{1-x} \] 我们把所有的 OGF 乘起来，发现其一定形如 \(\dfrac{(1+x)^p}{(1-x)^q}\)，其中 \(p,q\) 可以根据 \(y\) 计算得到。
分别考虑 \((1+x)^p\) 和 \(\frac{1}{(1-x)^q}\) 的展开形式，其分别为 \(\sum\limits_{i=0}^p\dbinom{p}{i}x^i\) 和 \(\sum\limits_{i=0}^{\infty}\dbinom{i+q-1}{q-1}x^i\) 。由于我们只需要求 \([x^n]\dfrac{(1+x)^p}{(1-x)^q}\)，所以只需要暴力 \(O(n)\) 计算两部分的卷积。
所以总复杂度为 \(O(nk)\)。
F - Revenge of BBuBBBlesort!
我们发现一次操作交换的两个数下标的奇偶性一定相同，所以如果一开始有一个偶/奇数的下标是奇/偶数一定无解。
我们把原序列按下标的奇偶性分为两个新序列。我们发现，对于在原序列上的一次交换，它使得原序列的逆序对个数减小了 \(3\)，而使得某一个新序列的逆序对个数减小了 \(1\)，所以必须保证两个新序列的逆序对之和的三倍等于原序列的逆序对个数（因为我们要保证最后两个新序列逆序对个数为 \(0\)）。
下面我们证明这两个条件都满足是充分的：考虑对新序列冒泡排序，那么每一次交换，其至多让原排列的逆序对个数下降 \(3\)，且如果能，一定等价于合法的对原序列的一次操作。由我们给出的前两个必要条件可知对两个新序列都冒泡排序后原序列有序，故每一次操作都一定让原序列的逆序对个数下降了 \(3\)，所以每一次操作都合法。
所以我们只需要上一个树状数组就可以了。
提交记录：#16951728,#16952239,#16964800,#16968538。