UOJ60 【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;
}