题解

思路

设整张票的数字和模 $k$ 为 $S$。某一位 $a_i$ 满足条件，等价于 $2a_i\equiv S\pmod k$。与其直接对“存在”做容斥，不如固定总和 $S$，统计完全不含任何合法数字的非幸运车票。

做法

子任务一

$k=1$ 时只有全零车票，且它一定幸运，答案为 $1$。

子任务二

枚举所有 $k^n$ 张车票，计算总和，再检查是否有一位满足 $2a_i\equiv S\pmod k$。

满分算法

枚举 $S=0,1,\ldots,k-1$。禁用所有满足 $2d\equiv S\pmod k$ 的数字 $d$，再做长度和模数的动态规划：

完成 $n$ 位后，$dp_{n,S}$ 就是总和为 $S$ 且没有任何一位能够见证幸运条件的车票数。所有非幸运车票按自身总和恰好被统计一次，因此

正确性说明

对任意车票，其总和模 $k$ 唯一确定为某个 $S$。若它含有满足 $2d\equiv S$ 的数字，则且仅则该位等于其余位之和，车票幸运；否则它被对应 $S$ 的动态规划统计为非幸运。两类互斥且覆盖全部 $k^n$ 张车票，故上述减法得到的正是答案。

复杂度

满分算法时间复杂度 $O(nk^3)$，空间复杂度 $O(k)$；枚举算法为 $O(nk^n)$。