UOJ60 【UR #5】怎样提高智商 题解

题目链接：#60. 【UR #5】怎样提高智商

题意：

共有 $n$ 道选择题，编号为 $1$ 到 $n$。第 $i$ 道题形如：（$h_i$ 为 “A” 或 “B” 或 “C” 或 “D”，$a_i, b_i, c_i, d_i$都是整数）

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

  A. $a_i$ 个 B. $b_i$ 个 C. $c_i$ 个 D. $d_i$ 个

求出所有 $n$ 道选择题的试卷中，正确答案最多的试卷。

例子：

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

  A. $0$ 个 ，B. $7$ 个 ，C. $1$ 个 ，D. $4$ 个

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

  A. $3$ 个 ，B. $2$ 个 ，C. $1$ 个 ，D. $4$ 个

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

  A. $0$ 个 ，B. $2$ 个 ，C. $1$ 个 ，D. $0$ 个

共有两种正确答案。一种可能的正确答案为：第一题选A，第二题选C，第三题选D。

输入格式：

共一行，包含一个正整数 $n$，表示试卷中选择题的个数。

输出格式:

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

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

这 $n$ 行中的第 $i$ 行包含 $h_i, a_i, b_i, c_i, d_i$，表示第 $i$ 道选择题。

$h_i$ 为 “A” 或 “B” 或 “C” 或 “D”，$a_i, b_i, c_i, d_i$ 都是整数且 $0 \leq a_i, b_i, c_i, d_i \leq 10^9$。

数据范围：

$n \le 10^5$

纯构造题，没什么规律可循。

先默认第一问 $h_1=\mathtt{A}$ ，ABCD都 $0$ 。

接着随便选BCD中的一个

不难发现发现此时如果 $h_2=\mathtt{A}$ ，则和第一问一模一样

然后第一问可以设置 $4$ 种情况，接下来的每一问都有 $3$ 种情况

总方案数 $4 \times 3^{n-1}$ 。构造一种么随便搞搞就好了。

更详细的可以参考这篇博客

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)())
const int mod = 998244353;

int qpow(int a,int b)
{
    int ans=1,base=a%mod;
    for(; b; b >>= 1)
    {
        if(b & 1) ans = ans * base % mod;
        base = base * base % mod;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    cout << 4*qpow(3,n-1)%mod << '\n';
    for(int i=1; i<=n; i++) cout << "A 0 0 0 0\n";
    return 0;
}