[uoj60]怎样提高智商

大力水手最近和他的女朋友奥利弗分手了，他感到人生非常灰暗，于是上山来找禅师解惑。

大力水手问禅师："大师，奥利弗以前经常说我是个笨蛋，让我觉得很生气。大概是因为我真的太笨了她才这么说吧。请问，怎样才能提高智商？"

禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这张试卷。”

大力水手拿到试卷，共有 $n$ 道选择题，编号为 $1$ 到 $n$。第 $i$ 道题形如：($h_i$ 为 "$\tt A$" 或 "$\tt B$" 或 "$\tt C$" 或 "$\tt D$"，$a_i, b_i, c_i, d_i$ 都是整数)

大力水手问禅师："是要我做这张试卷吗？"。禅师摆摆手，答："多想想。"

大力水手注意到一张试卷可能有很多种正确答案 (两种正确答案被认为是不同的当且仅当存在一道题这两份正确答案选的选项不同)，于是问禅师："是要我求这张试卷有多少种正确答案吗？"。禅师摆摆手，答："多想想。"

大力水手想到，一张试卷要是正确答案有很多种，就很容易蒙对，于是问禅师："是要我求出所有 $n$ 道选择题的试卷中，正确答案最多的试卷吗？"。禅师点点头，转身离去。

例子

输入格式

共一行，包含一个正整数 $n$ ($n \leq 10^5$)，表示试卷中选择题的个数。

输出格式

第一行一个整数，表示正确答案最多的试卷的正确答案数。你只用输出答案对 $998244353$ ($7 \times 17 \times 2^{23} + 1$，一个质数) 取模后的值。

接下来 $n$ 行输出一种正确答案最多的试卷。如果有多种你可以输出任意一种。

这 $n$ 行中的第 $i$ 行包含 $h_i, a_i, b_i, c_i, d_i$，表示第 $i$ 道选择题。$h_i$ 为 "$\tt A$" 或 "$\tt B$" 或 "$\tt C$" 或 "$\tt D$"，$a_i, b_i, c_i, d_i$ 都是整数且 $0 \leq a_i, b_i, c_i, d_i \leq 10^9$。

题解

由于要求正确答案尽可能得多，因此可以看出最大值一定满足 $a_i = b_i = c_i = d_i$，即四个选项的答案相同。(否则对任意一种答案，选定一道题目将四个选项都改为该答案答案就会更大)

接下来就是如何设置 $h_i$ 和 $a_i$ 的值了。可以看出，虽然四个选项都一样，但是不一定能都选，由于前面的选项对后面的选项是有影响的。

我们尝试着构造一下。第一题呢，由于不存在编号小于 $1$ 的题目，故我们的 $a_i = 0$，然后 $h_i$ 任意。即第一题的形式为 "$h_i$ 有 $0$ 个"。

然后是第二题。此时第一题已经选了一个选项，比如说你选了 $A$。那么第二题问什么比较好？问 "$A$ 有 $1$ 个"？这样第一题只能选 $A$ 了，如果问 "$A$ 有 $0$ 个"？这样第一题可以选 $B, C, D$，比较不错。如果我们用贪心地思想，那么就先选后者。

再思考一下第三题。此时前两题有 $12$ 种答案：($\tt BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD$)。发现里面能满足最多答案的条件应该是没有 $A$，因此我们的第三题仍然为 "$A$ 有 $0$ 个"。

以此类推，我们让所有 $n$ 道问题均为 "$A$ 有 $0$ 个"。这样的话，前 $n-1$ 题可以任意选择 $B, C, D$，而最后一题四个选项都可以选，故共有 $4 \cdot 3^{n-1}$ 种方案。

证明其实很简单。首先第一题只要等于 $0$ 就行。对于第二题，假如说它限制了字母 $A$，那么第一题就要么只能选 $B, C, D$，要么只能选 $A$ (为了满足第二题的条件)，故最多 $3$ 种方案。

同理，第三题也会限制一个字母，那么对于确定的第一题的选法，第二题至多只有 $3$ 种选择 (否则满足不了)。比如说第三题还是限制 $A = 0$，那么前两题一共有 $9$ 种；如果限制 $B = 0$，那么选择将更少，只有 $6$ 种。

类似地，每当前 $i-1$ 题的答案确定后，第 $i$ 题的答案至多只有 $3$ 种 (被第 $i+1$ 题的条件所限制，$1 \leq i < n$)，而最后一题的正确答案至多有 $4$ 种，因此方案数显然不超过 $3 \times 3 \times \cdots \times 3 \times 4 = 4 \cdot 3^{n-1}$，证毕。

因此这道题只是一个~~快速幂~~ (暴力) 的事情，然后输入 $n$ 行 A 0 0 0 0…… (注：我在 UOJ 上闲的蛋疼随机了一个字母……)

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod = 998244353;

ll PowerMod(ll a, int n, ll c = 1) {for(; n; n >>= 1, (a *= a) %= mod) if(n & 1) (c *= a) %= mod; return c;}

int main(){
	int n;
	for(scanf("%d", &n), printf("%lld\n", PowerMod(3, n - 1, 4)); n; --n) puts("A 0 0 0 0");
	return 0;
}

题目描述

$i$. 编号小于 $i$ 的题目中你一共选了几个 $h_i$？

例子

1. 编号小于 $1$ 的题目中你一共选了几个 $\tt B$？

2. 编号小于 $2$ 的题目中你一共选了几个 $\tt A$？

3. 编号小于 $3$ 的题目中你一共选了几个 $\tt D$？

输入格式

输出格式

题解

代码

坑