题解

思路

字符串长度最多为 $5$，所以可以把所有票片按“长度、数位和”分类计数。对于一对长度奇偶性不同的字符串，总长度为奇数，一定不合法。其余情况下，幸运票的中点要么落在左串内部，要么落在两个等长字符串的边界上，要么落在右串内部。

做法

先统计 cnt[len][sum]，表示给定票片中长度为 len、数位和为 sum 的字符串数量。

枚举一个长串 $x$，再枚举与它同奇偶性的较短长度 $l$：

• 当 $x$ 放在左侧时，中点位于 $x$ 内。设中点以前的 $x$ 前缀数位和为 $P$，$x$ 总数位和为 $S$，则右侧短串数位和必须为 $2P-S$。
• 当 $x$ 放在右侧时，中点位于 $x$ 内。设中点以前、属于 $x$ 的前缀数位和为 $P$，则左侧短串数位和必须为 $S-2P$。

两种需求都可在计数表中常数时间查询。长度相等时中点恰在连接处，只需在第一种计算中统计一次，避免重复。

正确性证明

任意合法有序对的两个长度必须同奇偶。若左串不短于右串，中点必在左串内部或连接边界上，算法第一种计算根据两半数位和相等式得到唯一所需的右串数位和，并统计且仅统计这些右串。若左串更短，中点严格位于右串内部，算法第二种计算同理得到唯一所需的左串数位和。

两种情况按长度大小互斥并覆盖全部有序对；等长情况只在第一种计算中出现一次。因此每个幸运有序对恰被统计一次，非幸运对不会满足相应等式，算法答案正确。

复杂度分析

设最大字符串长度为 $L=5$。时间复杂度为 $O(nL)$，空间复杂度为 $O(L^2)$；答案须使用 64 位整数。

子任务说明

• $n\le2000$ 时直接枚举 $n^2$ 个有序对。
• 所有字符串等长时，中点总在连接处，只需按数位和计数。
• 满数据按长度和数位和处理长串位于左右两侧的需求。