题解

思路

先根据同一字符计数向量能形成的不同排列数判断博弈胜负，再把“多项式系数为奇数”转化为二进制位无进位分配，最后用子集卷积计数。

做法

设各字母出现次数为 $a_1,\ldots,a_k$，相同计数向量共有

$$M=\frac{n!}{a_1!\cdots a_k!}$$

个不同排列。归纳分析游戏可得：$n$ 为奇数时所有字符串都是先手必胜；$n$ 为偶数时，恰好 $M$ 为奇数的字符串是败态。

由二进制下的 Kummer 定理，$M$ 为奇数当且仅当 $a_1+\cdots+a_k=n$ 的二进制加法不产生进位。也就是说，$n$ 的每个置位必须分配给恰好一个字母。

子任务 1

枚举全部 $k^n$ 个字符串，统计各字母次数并判断二进制无进位条件。

子任务 2

令 $s=\operatorname{popcount}(n)$，把 $n$ 的置位编号。对一个位集合 $S$，令 $v(S)$ 为这些二进制位表示的整数，权值为 $1/v(S)!$。

依次处理 $k$ 个字母，枚举当前字母取得的子集，可用 $O(k3^s)$ 的子集动态规划求出

$$\sum_{S_1\sqcup\cdots\sqcup S_k=U}\prod_i\frac1{v(S_i)!}.$$

乘以 $n!$ 即为败态字符串数。

子任务 3

上述表达式是函数 $f(S)=1/v(S)!$ 的 $k$ 次子集卷积在全集处的值。按集合大小分层做 Zeta 变换，把子集卷积变成每个掩码上的普通多项式乘法；对该多项式快速幂到 $k$ 次，再做 Möbius 逆变换即可。

最终答案为 $k^n$ 减去败态数；若 $n$ 为奇数则直接输出 $k^n$。

正确性

博弈归纳给出了败态与排列数奇偶性的等价关系。Kummer 定理保证多项式系数为奇数恰好对应所有置位无冲突分配。子集动态规划与分层子集卷积都逐一计入这些有序分配，并以 $n!/\prod a_i!$ 恢复每个计数向量对应的字符串数，因此计算出的败态数与定义一致。

复杂度

• 子任务 1：$O(k^n n)$；
• 子任务 2：$O(k3^s+n)$；
• 子任务 3：$O(s^2 2^s\log k+n)$；
• 空间复杂度为 $O(s2^s+n)$。