笔试时间：2023年4月13日 春招

第一题

题目：小红的好数组

小红定义一个数组为"好数组”，当且仅当该数组满足以下条件：

1、数组仅由0、1、2三种元素组成；

2、数组相邻的元素不相等。

例如:121.2.0.1是好数组。小红定义一个数组的“陡峭值"”为该数组相邻元素的差的绝对值之和。

例如，[2,1,2,0,1]的陡峭值为|2-1|+|1-2|+|2-0|+|0-1| = 5。小红想知道，长度为n的所有好数组的陡峭值之和是多少? 由于答案过大，请对10^7取模。

样例输入

2

样例输出

8

解释：

共有[0,1],[1,0],[0,2],[2,0],[1,2],[2,1]这六个好数组。陡峭值之和为1+1+2+2+1+1=8

参考题解

f(n) = (n-1)*2^(n+1)

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>

using namespace std;

long long fastMi(long long x, long long n, long long m) {
    long long res = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            res = (res * x) % m;
        }
        x = (x * x) % m;
        n /= 2;
    }
    return res;
}

int main() {
    long long n;
    cin >> n;
    long long mod = 1000000007;
    long long ans = ((n - 1) * fastMi(2, n + 1, mod)) % mod;
    cout << ans << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static long fastMi(long x, long n, long m) {
        long res = 1;
        while (n > 0) {
            if (n % 2 == 1) {
                res = (res * x) % m;
            }
            x = (x * x) % m;
            n /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long mod = 1000000007;
        long ans = ((n - 1) * fastMi(2, n + 1, mod)) % mod;
        System.out.println(ans);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def fastMi(x, n, m):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = res * x % m
        x = x * x % m
        n //= 2
    return res

n = int(input())
mod = 10**9 +7
ans = ((n-1) * fastMi(2, n + 1, mod)) % (mod)
print(ans)

第二题

题目：小红的二叉树

小红拿到了一颗二叉树，定义每个节点的价值为子树节点乘积的末尾0的数量。现在请你返回一颗二叉树，树的结构和给定二叉树相同，将每个节点的权值替换为该节点的价值。二叉树的节点不超过10^5。二叉树每个节点的权值都是不超过10^9的正整数。

样例输入

{2,5,10,#,#,4,5}

样例输出

{3,0,2,#,#,0,0}

小红拿到的树

2

/ \

5 10

/ \

4 5

需要返回的树

3

/ \

0 2

/ \

0 0

参考题解

二叉树遍历

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    struct Counts {
        int count2;
        int count5;

        Counts(int c2, int c5) : count2(c2), count5(c5) {}
    };

    struct TreeNode {
        i