题解

思路推导

设所有数字之和模 $k$ 为 $s$。某一位数字 $x$ 能证明车票幸运，当且仅当 $2x\equiv s\pmod k$。因此可以固定总和余数，反过来统计没有任何一位满足这个同余式的车票。

当 $k$ 为奇数时，乘二在模 $k$ 意义下是双射。每个 $s$ 恰有一个被禁止的数字。利用循环群上的容斥或单位根筛，可把所有余数的非幸运车票总数化为

$(k-1)^n+(-1)^n(\gcd(n+k-2,k)-1)$。

当 $k$ 为偶数时，只有偶数余数可能有解，并且每个有解余数对应两个相差 $k/2$ 的数字。把数字按模 $k/2$ 配对后，同样的计数给出中等版所需闭式。

做法

小范围直接枚举全部 $k^n$ 张车票。中等范围枚举总和余数 $s$，删去满足 $2x\equiv s\pmod k$ 的数字，再用余数动态规划统计总和为 $s$ 的非幸运序列。满分范围按 $k$ 的奇偶代入闭式，并用快速幂计算。

正确性证明

固定一张车票及其总和余数 $s$。它幸运等价于至少一位 $x$ 满足 $2x\equiv s\pmod k$，所以中等做法对每个 $s$ 统计的恰是总和为 $s$ 且所有位都避开对应禁用集合的非幸运车票。各个 $s$ 互不重叠，故用全部 $k^n$ 张车票减去它们即得答案。

奇数 $k$ 时禁用集合恒为一个元素；偶数 $k$ 时，奇数 $s$ 的禁用集合为空，偶数 $s$ 的禁用集合恰为两个相差 $k/2$ 的元素。对循环余数计数作单位根筛后，非零频率的贡献只在相位周期整除相应指数时保留，保留频率的数量分别为题解公式中的最大公约数。因此闭式与上述逐余数动态规划统计同一集合，满分算法正确。

复杂度分析

中等算法的时间复杂度为 $O(nk^3)$，空间复杂度为 $O(k)$。满分算法只进行常数次快速幂与最大公约数运算，时间复杂度为 $O(\log n+\log k)$，空间复杂度为 $O(1)$。