思路与方法

1. 可行性分析

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

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

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

P2909.第3题-合法字符串

1000ms

Tried: 8

Accepted: 4

Difficulty: 7

所属公司 : 阿里

算法与标签>数学

题目内容

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

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

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

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

输入描述

输入一个整数 $n(1≦n≦10^9)$ 代表字符串长度。

输出描述

输出一个整数，代表所有长度为 $n$ 的字符串的 $f(s)$ 之和。由于答案可能很大，请将答案对 $998$ $244$ $533$ 取模后输出。

样例1

输入

输出

说明

在这个样例中，当 $n =2$ 时，全部的合法字符串有：

“ $00$ ”，由于不需要任何操作， $f=0$ ；
” $01$ “，无法变为全 $0$ ，不计；
“ $10$ ”，无法变为全 $0$ ，不计；
“ $11$ ”，操作一次即可，所以 $f=1$ 。

样例2

输入

输出

样例3

输入

输出

528897405

编辑器加载中…

输入

预期输出（选填）

思路与方法

1. 可行性分析

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

P2909.第3题-合法字符串

题目内容

输入描述

输出描述

样例1

样例2

样例3

Status

Development

Support

About