有一个 $n\times n$ 的棋盘，你要在上面放最少数量的”半皇后“，使得每个格子都能被攻击到。

一个位于 $(x,y)$ 的 ”半皇后“ 能攻击到 $(a,b)$ 当且仅当满足以下条件中至少一个：

• $a=x$；
• $b=y$；
• $a-b=x-y$；

输出方案。

$1\le n\le 10^5$。

给定 $n$，求满足以下条件的集合 $S\in\{0,1,2,\dots,2^n-1\}$ 的个数：

对于所有 $S$ 的非空子集 $T\in S$，$T$ 均满足以下条件中的至少一个：

• $|T|$ 是奇数；
• $T$ 中元素的异或和非零；

对 $998244353$ 取模。

$1\le n\le 2\times 10^5$。

给定一个整数 $K$。求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。

$2 \le K \le {10}^5$。

给定 $n$，求

$\sum\limits_{m>0,a_i>0,\sum a_i=n}\prod_{i=1}^m F_{a_i}$

对 $10^9 + 7$ 取模。

$1\le n\le 10^{100}$。

你有 $n$ 个数 $a_1,a_2,\dots,a_n$ 要进行 $k$ 次操作，每次随机选择一个数 $x \in [1,n]$，把 $a_x$ 减一，并将答案增加除 $a_x$ 外所有数的乘积。

求最终答案的期望，答案对 $10^9 + 7$ 取模。

$1\le n\le 5000$。

给定一个长 $n$，值域 $[1,n]$ 的数组 $a$，定义 $a$ 的排列（任意打乱元素顺序后的数组）$b$ 的价值为最小的操作次数使得 $b=a$，一次操作可以：

• 选定两个 $1\le i<j\le n$，交换 $b_i$ 和 $b_j$；

F1：给定 $a$，构造价值最大的 $b$；

F2：给定 $a$ 和 $b$，判断 $b$ 的价值是否最大；

$1\le n\le 2\times 10^5$。

给定一个 $1\sim n$ 的排列 $p$。

对于一个 $1\sim n$ 的排列 $q$，定义其权值为：

$|q_1-p_{q_2}|+|q_2-p_{q_3}|+|q_3-p_{q_4}|+\cdots+|q_{n-1}-p_{q_n}|+|q_n-p_{q_1}|$

找出 任意一个 权值最小化的 $1\sim n$ 的排列 $q$。

$2\le n\le 200$。