辉夜姬的十道难题

妹红最近玩了一款叫 $2048$ 的小游戏。  (图为个人无撤销最高纪录~ 纯手玩)。

$2048$ 是一个非常简单的数字游戏，它在 $4\times 4$ 的棋盘上进行，通过移动来合并数字，达到 $2048$ 即算胜利。妹红最近沉迷上了这个游戏，事情传到辉夜那里后，辉夜决定用曾经无人破解的十道难题来考考妹红。 游戏规则： 1. 游戏在 $n\times m$ 的方格棋盘上进行。 2. 两个玩家，其中一个可以移动棋盘上的数字，记做 M，另外一个可以向棋盘上放数字，记做 C。 3. 移动数字的规则如下：可以向上/下/左/右四个方向的其中之一移动。选定好方向后，所有数字都会向该方向靠拢，相同的两个数字相撞时会合并成一个新数字，这个数字是它们的和。在一次移动中，每个数字最多只能合并一次，优先合并靠近移动方向棋盘边缘的数字。 以 $n=2,m=4$ 的情况举例如下（$0$ 表示该位置为空）： ``` 2 2 2 2 2 2 0 2 ``` 向左移动后变为： ``` 4 4 0 0 4 2 0 0 ``` 每次合并后，将会获得一定的分数，获得的分数等于所有合并后数字相加之和。若无任何合并发生，则不得分。在上例中，得分为 $12$。 移动前后，若棋盘上的所有数字大小和位置均没有变化，则不算做有效移动，否则即是有效移动。 4. 向棋盘放置数字的规则如下：只能选择棋盘上没有数字的位置放置一个数字，可以放置的数字和放置方法在每个子任务中会具体描述。 5. 游戏开始时棋盘为空，分数为 $0$。先由玩家 C 行动两步，接着玩家 M 和 C 轮流行动，中间的每一步都必须是有效的。当轮到玩家 M 时，若不能够进行有效移动，则游戏结束，此时的得分为最终得分。 本题目为提交答案题，共有 $10$ 个子任务需要你来完成。将你的答案写到 $10$ 个文件中，分别命名为 ```gamex.out```，$x$ 表示子任务的编号（$0\ldots 9$）。 子任务内无部分分，你可以得到该任务的分数当且仅当你的输出和标准答案完全相同。 十道难题如下: 0. $n=1,m=2$。玩家 C 行动时可以放置 $2$ 或 $4$。若用 $x$ 表示在一局游戏中玩家 M 最多可以行动 $x$ 次，那么这个 $x$ 的最值是多少？输出两行，第一行一个整数表示 $x$ 的最小值，第二行一个整数表示 $x$ 的最大值。 1. $n=10738029,m=921023$。玩家 C 行动时可以放置 $2$ 或 $4$。若用 $x$ 表示棋盘上所有数字之和，请问 $x$ 的最大值是多少。因为这个值可能过大，只需要输出它除以 $10^9+7$ 的余数即可。 2. $n=2,m=2$。玩家 C 行动时可以放置 $2,4$。用 $x$ 表示目标数字， $x$ 一定为 $2$ 的正整数幂。玩家 M 的目标是使盘面上出现大于等于数字 $x$ 的数，玩家 C 的目标是在盘面上出现数字 $x$ 之前使游戏结束。在两方均最优决策的情况下，求一个最大的 $x$，使得玩家 M 能达到自己的目标。 3. $n=4,m=4$。玩家 C 行动时可以放置 $2,4$。输出两行，每行一个数字。第一行的数字表示能达到的最大分数。第二行的数字表示当数字总和达到最大时，分数的最小值。 4. $n=7393,m=9133$。玩家 C 可以放置数字 $2$ 共 $6144$ 次。棋盘初始为空，初始分数为 $0$。首先由玩家 C 连续行动，直到用完所有放置机会或中途主动放弃。然后连续向上移动直到向上方向不能构成有效移动。输出一行一个整数，表示最大得分。 5. $n=7,m=233$。初始分数为 $0$,玩家 C 可以放置数字 $2$ 共 $233$ 次，数字 $4$ 共 $66$ 次。棋盘第一行一开始有若干数字，第 $i$ 列的数字为 $\text{lowbit}(i)\times 2$，$\text{lowbit}(i)$ 表示数字 $i$ 的二进制形式只取最后一个 $1$ 构成的数字。如 $\text{lowbit}(1\ldots 8)$ 为 $1,2,1,4,1,2,1,8$。棋盘的其他位置均为空。首先由玩家 C 连续行动，直到用完所有放置机会或中途主动放弃。然后连续向上移动直到向上方向不能构成有效移动。输出一行一个整数，表示最大得分。 6. $n=3,m=3$。玩家 C 行动时可以放置 $2,4$。用 $x$ 表示目标数字，$x$ 一定为 $2$ 的正整数幂。玩家 M 的目标是使盘面上出现数字 $x$，玩家 C 的目标是在盘面上出现数字 $x$ 之前使游戏结束。在两方均最优决策的情况下，输出一个最大的 $x$，使得玩家 M 能达到自己的目标。 7. $n=3,m=3$。玩家 C 行动时可以放置 $2,4$。玩家 M 的目标是让得分最大化，玩家 C 的目标是让得分最小化，在两方均最优决策的情况下，输出一个整数，表示最终的分数。 8. $n=3,m=3$。玩家 C 行动时，有 $90\%$ 的几率放置一个 $2$，$10\%$ 的几率放置一个 $4$，放置在各个空位的几率均等。用 $x$ 表示目标数字，玩家 M 的目标是使盘面上出现大于等于数字 $x$ 的数。在玩家 M 最优决策的情况下，输出一行，$9$ 个实数，四舍五入到小数点后 $2$ 位，用空格隔开，分别表示 $x=2,4,8,16,32,64,128,256,512$ 时，达成目标数字的概率。 9. $n=3,m=3$。玩家 C 行动时，有 $90\%$ 的几率放置一个 $2$，$10\%$ 的几率放置一个 $4$，放置在各个空位的几率均等。玩家 M 的目标是让分数最大化。在玩家 M 最优决策的情况下，输出一个实数，四舍五入保留整数，表示分数的期望值。 妹红虽然对 $2048$ 有一定了解，但她并不能解决全部的问题，于是就交给了学 OI 的你。

见题目描述

见题目描述

样例任务（无需提交）:
 n=2,m=2。 玩家C行动时只可以放置2。请输出一个整数，表示棋盘上可能出现的最大数字。

16

如果对移动规则有疑惑，可以到 $2048$ 网站进行尝试: http://gabrielecirulli.github.io/2048/ by-orangebird