https://uoj.ac/contest/7/problem/60

做法

非常有意思的一道题目，结论不难猜，但是非常难证。

首先，答案为 $4*3^{n-1}$ ，达到上界也非常的简单，搞一堆 ‘A 0 0 0 0’ 就行了。

时间复杂度：$O(n)$ 。

证明

我们认为如果一道题目的四个答案都是一样的，我们称其为 SB 题。

假设最早出现的 SB 题在第 $i$ 道。

那么显然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL mod=998244353;
int n;
int main(){
    scanf("%d",&n);
    LL ans=4;
    for(int i=2;i<=n;i++)ans=ans*3%mod;
    printf("%lld\n",ans);
    for(int i=1;i<=n;i++)printf("A 0 0 0 0\n");
    return 0;
}