荣耀

两个小时，3道编程题

第一题：数学¶

题目描述¶

N个不同的字符可以组成多少ID，其中ID需要满足以下条件：任何ID的长度需要大于等于1且小于等于L个字符. 比如：当N = 2（假设字符可以是0或1），并且L = 3时，他具有如下的ID : {0,1,00,01,10,11,000,001,010,011,100,101,110,111}, 因此当N=2,L=3时总共有14种ID。

需要编写一个程序，找到可能的ID的总数。由于答案可能非常大，最后的结果需要对1000000007取余请使用Java实现

输入描述：输入包含多个用例。每个用例将为包含两个整数N和L的一行。N是可以作为id的一部分的字符数，L是该语言支持的最大长度（1<= N <=65535,1 0<= L <=10 ^ 5）。

当N=0并且L等于0时表示输入结束。

输出描述：对每个用例输出一行ID的总数

示例：输入： 2 3 100 15 0 0

输出： 14 979451521

解题思路¶

需要计算使用 N 个不同的字符，长度在 1 到 L 之间的所有可能的 ID 数量。由于字符可以重复使用，每个位置上都有 N 种选择。

问题转化：

对于长度为 1 的 ID，有 $N^1 = N$ 种可能。
对于长度为 2 的 ID，有 $N^2$ 种可能。
...
对于长度为 L 的 ID，有 $N^L$ 种可能。

因此，总的 ID 数量就是一个等比数列的和：

$$ 总数= N^1 + N^2 + ......+N^L $$ 等比数列求和公式：

对于首项为 $a_1$，公比为 $q$，项数为 $n$ 的等比数列，其和为：

\[ S_n = \frac{a_1 (q^n - 1)}{q - 1} \]

在我们的情况下：

首项 $a_1=N$
公比 $q=N$
项数 $n=L$

代入公式，我们得到：

\[ 总数 = \frac{N (N^L - 1)}{N - 1} \]

为了方便计算，我们也可以将公式稍微变形：

\[ 总数= \frac{N^{L+1} - N}{N - 1} \]

特殊情况处理：

当 $N=1$时，公式中的分母为零，需要单独处理。
- 在这种情况下，所有长度的 ID 数量都是 1，所以总数为 L。

模运算注意事项：

由于答案可能非常大，需要对 $10^9 + 7$ 取模。

在计算过程中，需要注意防止负数出现，所以在做减法时，可以先加上一个模数。

计算步骤：

计算分子：

$$ numerator=(N^{L+1} - N + \text{MOD}) \mod \text{MOD} $$ - 这里的 $MOD= 10^9 + 7$ - 使用快速幂算法计算 $N^{L+1} \mod \text{MOD}$ 2. 计算分母的模逆元：
- 分母为 $N−1$
- 需要计算 $(N-1)$ 在模 $\text{MOD}$ 下的逆元
- 使用费马小定理，因为 $\text{MOD}$ 是质数 $$ inverseDenominator=(N - 1)^{\text{MOD} - 2} \mod \text{MOD} $$
- 计算最终结果： $$ result=(\text{numerator} \times \text{inverseDenominator}) \mod \text{MOD} $$

代码实现¶

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    // 快速幂算法，计算 (base^exp) % mod
    static long powMod(long base, long exp, int mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0) { // 如果 exp 是奇数
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            exp >>= 1; // exp = exp / 2
        }
        return result;
    }

    // 计算模逆元，使用费马小定理
    static long modInverse(long a, int mod) {
        return powMod(a, mod - 2, mod);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            long N = sc.nextLong();
            long L = sc.nextLong();

            if (N == 0 && L == 0) {
                break;
            }

            if (N == 1) {
                System.out.println(L % MOD);
            } else {
                long numerator = (powMod(N, L + 1, MOD) - N + MOD) % MOD;
                long denominator = N - 1;
                long inverseDenominator = modInverse(denominator, MOD);
                long result = (numerator * inverseDenominator) % MOD;
                System.out.println(result);
            }
        }

        sc.close();
    }
}

第二题：数学¶

题目描述¶

计算输入复数的绝对值

输入描述：两个输入，第一个是复数的实部，第二个是复数的虚部

输出描述：绝对值（打印出整数即可）

示例：输入： 7308 1839

输出： 7536

解题思路¶

要计算复数的绝对值，给定实部 aaa 和虚部 bbb，其公式为：

$$ |z| = \sqrt{a^2 + b^2} $$ 然后取其整数部分进行输出。

代码实现¶

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取复数的实部和虚部
        int real = sc.nextInt();
        int imag = sc.nextInt();

        // 计算复数的绝对值
        double magnitude = Math.sqrt((double) real * real + (double) imag * imag);

        // 对结果进行四舍五入，输出整数部分
        System.out.println((int) Math.round(magnitude));
    }
}

第三题：模拟¶

题目描述¶

实现一个简易行编辑器，根据编辑指令输出最后结果。编辑指令包括以下几种：

i指令，在指定行前插入一行

a 指令，在指定行后增加一行

r指令，整体替换指定行

d指令，删除指定行

| 指令，前面几条指令通过该指令可执行复合操作，前一条指令的输出作为后一条指令的输入。

输入描述：程序以一个字符串作为输入，此字符串可以是一条指令，也可以是多条指令组合成的复合指令：

a 、i、r指令格式：行号指令名行内容

d 指令格式：行号指令名

|指令格式：指令1|指令2|指令3|…

行号、指令名、行内容之间以空格分离，行号表示对该指定行做编辑操作

初始状态下，行号为1，只能执行i指令，否则指令错误

行号从1开始计数，并且小于等于当前总行数，否则指令错误

其它指令为错误指令

行内容不考虑换行

复合指令下，不考虑行内容中包括“|”的情况

输出描述：如果指令错误，打印”error”

如果正确执行，打印指令执行的最后结果

示例1：输入： 1 i first line|1 a second line|2 r replace a line

输出： first line replace a line

示例2：输入： 1 a first line|1 a second line 输出： error

代码实现¶

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取整行输入
        String inputLine = sc.nextLine();

        // 按照"|"分割指令
        String[] commands = inputLine.split("\\|");

        // 初始化编辑器内容
        List<String> editor = new ArrayList<>();

        // 逐个执行指令
        for (int idx = 0; idx < commands.length; idx++) {
            String commandStr = commands[idx].trim();

            // 如果指令为空，跳过
            if (commandStr.isEmpty()) {
                continue;
            }

            // 按空格分割指令，限制为3个部分
            String[] parts = commandStr.split(" ", 3);

            // 检查指令格式是否正确
            if (parts.length < 2) {
                System.out.println("error");
                return;
            }

            // 解析行号
            int lineNumber;
            try {
                lineNumber = Integer.parseInt(parts[0]);
            } catch (NumberFormatException e) {
                System.out.println("error");
                return;
            }

            String commandName = parts[1];

            // 行号必须大于等于1
            if (lineNumber < 1) {
                System.out.println("error");
                return;
            }

            // 处理指令
            switch (commandName) {
                case "i":
                    // 插入操作需要有行内容
                    if (parts.length < 3) {
                        System.out.println("error");
                        return;
                    }
                    // 初始状态下，只有i指令可以执行
                    if (editor.isEmpty() && idx == 0 && lineNumber == 1) {
                        editor.add(0, parts[2]);
                    } else {
                        if (lineNumber > editor.size() + 1) {
                            System.out.println("error");
                            return;
                        }
                        editor.add(lineNumber - 1, parts[2]);
                    }
                    break;
                case "a":
                    // 添加操作需要有行内容
                    if (parts.length < 3) {
                        System.out.println("error");
                        return;
                    }
                    // 初始状态下不能执行a指令
                    if (editor.isEmpty()) {
                        System.out.println("error");
                        return;
                    }
                    if (lineNumber > editor.size()) {
                        System.out.println("error");
                        return;
                    }
                    editor.add(lineNumber, parts[2]);
                    break;
                case "r":
                    // 替换操作需要有行内容
                    if (parts.length < 3) {
                        System.out.println("error");
                        return;
                    }
                    if (lineNumber > editor.size()) {
                        System.out.println("error");
                        return;
                    }
                    editor.set(lineNumber - 1, parts[2]);
                    break;
                case "d":
                    // 删除操作
                    if (parts.length != 2) {
                        System.out.println("error");
                        return;
                    }
                    if (lineNumber > editor.size()) {
                        System.out.println("error");
                        return;
                    }
                    editor.remove(lineNumber - 1);
                    break;
                default:
                    // 非法指令
                    System.out.println("error");
                    return;
            }
        }

        // 输出最终结果
        for (String line : editor) {
            System.out.println(line);
        }
    }
}