1000ms

Difficulty: 7

所属公司 : 阿里

时间 :2025年4月24日-阿里淘天(开发岗)

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库阿里系机考题库，可解锁完整内容。

购买阿里系机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（阿里系机考题库），可解锁完整内容。

购买题库开通会员

思路与方法

1. 可行性分析

每次操作：选取两个相邻字符，翻转后交换（“00”↔“11”，“01”↔“10”）。
注意：操作前后“1 的个数”模 2 不变。
因此只有当字符串中 1 的个数 $M$ 为偶数时，才有可能通过若干次操作变为全 0；否则无解，不计入和。

2. 单串最优操作数 $f(s)$

若 $s$ 中有偶数个 1，记其位置（从左到右）为 $p_1<p_2<\cdots<p_M$ 。

题目内容

对于仅由 $0$ 和 $1$ 两种字符组成的字符串 $s$ ,定义一次操作为：

选择两个相邻字符，将它们同时取反（即如果字符原本为 $0$ ，将其变成 $1$ ；如果字符原本为 $1$ ，将其变成 $0$ ）。

记 $f(s)$ 为将 $s$ 变为全 $0$ 所需的最少操作次数。若无法变为全 $0$ ，则该字符串的 $f(s)$ 不计。

现在，给定整数 $n$ ，求所有长度为 $n$ 的合法字符串的 $f(s)$ 之和。由于答案可能很大，请将答案对 $998$ $244$ $533$ 取模后输出。