第一题
问题描述
电影院共有n行，m列座位。部分座位已被陌生人提前购买，剩余座位为空闲。你和你的k 位朋友希望一起观影，选座时有以下要求：
•只能选择空闲座位：
•全部k个人的选座需要位于同一行，且保持连续；
•对于选中的每一个位置，其上下左右相邻的位置要么不存在，要么为空闲，要么同样为你们选中的位置。
现在，给出电影院的座位示意图，以及多次询问每次询问给出k 个整数，表示你们希望一起观影的人数，请计算对于每次询问，有多少种不同的选座方案满足上述要求。两个方案不同当且仅当至少有一个人与之前的位買不同。若不存在任何合法方案，输出0。由于答案可能很大，请将答案对998244353 取模后输出
输出描述
对于每次询问，在一行上连续的输出一个整数，表示不同的选座方案数。由于答案可能很大，请将答案对 998244353 取模后输出。
第二题
问题描述
小红有一个长度为 n 的数组 {a1, a2,…,an}。她可以对数组进行若干次操作，每次操作步
骤：
- 选择一个区间[l，r]，即子数组{al, al+1,…, ar}
- 将该子数组中的所有元素以任意顺序重新排序；
- 本次操作需支付代价：
请你分别计算出：
•进行若千次操作后，使得新的数组按小到大排序的最小代价；
•进行若千次操作后，使得新的数组按大到小排序的最小代价。
输入描述
输出描述
在一行上输出两个整数，分别表示将原数组按小到大排序的最小代价,将原数组按大到小排序的最小代价。
第三题
问题描述：
对于仅由0和1两种字符组成的字符串 5，定义一次操作为：
•选择两个相邻字符，将它们同时取反（即如果字符原本为0，将其变成1；如果字符原本为1，将其变成0）
•记f（s）为字符串 s变全0所需的最少操作次数。如果无法变成全0，则该字符串的f(S）不
计
现在，给定一个整数 n，求所有长度为 n 的合法字符串的 f(S）之和。由于答案可能很大，请将答案对 998 244 353 取模后输出。
输入描述：
输入一个整数n (1 ≤ n ≤ 10^9），表示字符串长度。
输出描述：
输出一个整数，代表所有长度为 n 的合法字符串的f（S）之和。由于答案可能很大，请将答案对 998 244 353 取模后输出