题解:首先,如果每组有偶数个整数,显然将首尾的数不断成对压进每组就能满足条件.
令每组的整数数量为 $m$,我们只要处理 $m=3$ 的情况就可以了,因为剩下的情况都可以处理前 $3$ 项之后转化成第一种情况.
题意:求$k$个数字的八进制数满足是$p$的倍数且每个数字出现次数都是3的倍数的数字有多少个.
题解:$dp[k][i][p]$ 表示状态压缩三进制 $i$ 和模等于 $p$ 的 $k$ 位数字有多少个.然后考虑倍增+卷积运算.这里的卷积是 3进制不进位加法的卷积.有个技巧是只做首尾两次 fwt 和 rfwt,因为fwt运算只涉及到加法
题意:判断十五数码问题是否无解.
直接大力猜结论,大概模拟一下 $0$ 位置的变动.
根据 $0$ 所在位置的行列奇偶性和分行和列的逆序对数量奇偶行相同即可.
题解:利用主席树可以维护一个区间里面一段值域里面元素的个数.
我们先把 $4000$ 以内的数暴力处理掉,剩下的数就只能是某个数的整数次方了,从大到小判断开 $x$ 次方是不是整数就好了.