✅ 秋招备战指南 ✅

💡 学习建议：

• 先尝试独立解题
• 对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力

🌸 目前本专栏已经上线160+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

题目一：小兰的艺术字体设计

1️⃣：分析数字"美学空洞"的分布规律，使用数位贡献法分别计算首位和非首位的贡献

2️⃣：利用快速幂计算大指数的幂次，处理模运算避免溢出

难度：中等

这道题目的关键在于理解如何统计指定长度数字的各位数字贡献总和。通过将问题分解为首位贡献和非首位贡献两部分，结合数学公式推导，可以得到一个高效的 O(log n) 解法，避免了枚举所有数字的暴力做法。

题目二：小基的神秘密码验证

1️⃣：分析镜像三联码的构造规律，发现其结构完全由前1/3段决定

2️⃣：预处理所有可能的有效密码，使用二分查找快速统计区间内的个数

3️⃣：利用回文串的对称性质，推导出A=C且B=reverse(A)的构造规律

难度：中等

这道题目结合了字符串处理和数学推理，需要深入理解回文串的性质和约束条件。通过数学分析发现镜像三联码的构造规律，将问题转化为预处理+二分查找，实现了高效的区间统计。

题目三：小柯的团队协调计划

1️⃣：转化条件max(a,b,c,d)=lcm(a,b,c,d)为d的因子选择问题

2️⃣：使用筛法预处理每个数的真因子个数

3️⃣：利用组合数学计算方案数，通过前缀和优化查询效率

难度：中等偏难

这道题目需要深入理解最大值与最小公倍数相等的数学含义，并设计高效的因子统计算法。通过数学转化将问题简化为因子选择和组合计数，利用预处理和前缀和技术实现 O(N log N) 预处理，O(1) 查询的高效解法。

01. 小兰的艺术字体设计

小兰是一位著名的字体设计师，她最近在设计一套新的艺术数字字体。在这套字体中，每个数字都有独特的造型，其中一些数字包含封闭的圆形区域（她称之为"美学空洞"）。

根据小兰的设计稿，各个数字的"美学空洞"数量如下：

数字	0	1	2	3	4	5	6	7	8	9
空洞数	1	0	0	0	1	0	1	0	2	1

• 数字 有 个空洞

• 数字 、、、、 没有空洞

• 数字 、、 各有 个空洞

• 数字 有 个空洞

现在，小兰想要了解，对于所有恰好包含 位且没有前导零的正整数，它们的"美学空洞"总数是多少。请你帮助小兰计算这个值。

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 （）代表数据组数，每组测试数据描述如下：

在单独的一行输入一个正整数 （），表示小兰询问的数字的位数长度。

输出格式

对于每组测试数据：

在单独的一行输出一个正整数表示所有长度为 的数字的"美学空洞"之和。

（由于答案可能很大，因此请输出结果对 取模的值。）

样例输入

2
1
2

样例输出

6
104

数据范围

• 

• 

样例	解释说明
样例1	长度为 且不含前导零的数字包括：（注意：单独的 不算前导零），其"空洞数"总和为：
样例2	长度为 的数字从 到 ，共 个数字，需要统计所有这些数字中各位数字的空洞总和

题解

这道题的关键在于理解如何统计所有指定长度数字的"美学空洞"总数。

首先分析问题：

• 对于长度为 的数字，范围是从 到
• 需要计算这个范围内所有数字各位上的空洞数总和

可以按照数位贡献来分别计算：

1. 首位数字的贡献：首位只能是 到 ，每个数字在首位出现 次

   • 首位空洞总数 =

2. 非首位数字的贡献：每个非首位可以是 到 ，对于 位数，除了首位还有 个位置

   • 在任意非首位，每个数字 到 都出现 次
   • 单个非首位的空洞总数 =
   • 总共有 个非首位，所以总贡献 =

因此最终答案为：

由于 可能很大（），需要用快速幂计算 和 。

时间复杂度：每个查询 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()

MOD = 998244353

def pow_mod(base, exp, mod):
    # 快速幂计算 base^exp % mod
    res = 1
    base %= mod
    while exp > 0:
        if exp & 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return res

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        if n == 1:
            # 特殊情况：个位数 0-9 的空洞总和
            print(6)
            continue
        
        # 计算 10^(n-1) % MOD 和 10^(n-2) % MOD
        pow_n1 = pow_mod(10, n - 1, MOD)
        pow_n2 = pow_mod(10, n - 2, MOD)
        
        # 首位贡献：5 * 10^(n-1)
        part1 = (5 * pow_n1) % MOD
        
        # 非首位贡献：6 * 9 * (n-1) * 10^(n-2)
        part2 = (6 * 9 % MOD * ((n - 1) % MOD) % MOD * pow_n2) % MOD
        
        ans = (part1 + part2) % MOD
        print(ans)

solve()

Cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;

// 快速幂计算 base^exp % mod
ll pow_mod(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            res = (__int128)res * base % mod;
        }
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        ll n;
        cin >> n;
        
        if (n == 1) {
            // 特殊情况：个位数 0-9 的空洞总和
            cout << 6 << "\n";
            continue;
        }
        
        // 计算 10^(n-1) 和 10^(n-2)
        ll pow_n1 = pow_mod(10, n - 1, MOD);
        ll pow_n2 = pow_mod(10, n - 2, MOD);
        
        // 首位贡献
        ll part1 = (5LL * pow_n1) % MOD;
        
        // 非首位贡献
        ll part2 = (6LL * 9 % MOD * ((n - 1) % MOD) % MOD * pow_n2) % MOD;
        
        ll ans = (part1 + part2) % MOD;
        cout << ans << "\n";
    }
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static final long MOD = 998244353;
    
    // 快速幂计算 base^exp % mod
    static long powMod(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = base * base % mod;
            exp >>= 1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine());
            
            if (n == 1) {
                // 特殊情况：个位数 0-9 的空洞总和
                System.out.println(6);
                continue;
            }
            
            // 计算 10^(n-1) 和 10^(n-2)
            long powN1 = powMod(10, n - 1, MOD);
            long powN2 = powMod(10, n - 2, MOD);
            
            // 首位贡献
            long part1 = (5L * powN1) % MOD;
            
            // 非首位贡献
            long part2 = (6L * 9 % MOD * ((n - 1) % MOD) % MOD * powN2) % MOD;
            
            long ans = (part1 + part2) % MOD;
            System.out.println(ans);
        }
    }
}

02. 小基的神秘密码验证

小基 是一名密码学专家，她设计了一套独特的密码验证系统。在这个系统中，只有满足特殊规律的数字序列才能通过验证。

小基 定义了一种名为"镜像三联码"的特殊密码格式：

1. 密码序列的长度必须是 的倍数
2. 将整个序列从左到右等分为三段：、、
3. 前两段连接后（）必须构成回文序列
4. 后两段连接后（）必须构成回文序列

只有同时满足这四个条件的数字序列，才能被小基的系统识别为有效的"镜像三联码"。

现在，小基想要知道在给定的数值区间 内，有多少个正整数的十进制表示（不含前导零）能够构成有效的"镜像三联码"。

输入格式

每个测试文件均包含多组测试数据。

第一行输入一个整数 （），表示测试数据的组数。

此后 行，每行输入两个整数 （），表示查询区间。

输出格式

对于每组测试数据，新起一行，输出一个整数，表示区间内满足"镜像三联码"格式的正整数个数。

样例输入

3
1 100
1 1000
100 300

样例输出

0
9
2

数据范围

• 

• 

样例	解释说明
样例1	在区间 中，没有数字能够构成有效的镜像三联码（因为需要至少3位数，且满足特殊回文条件）
样例2	在区间 中，有 个数字能够构成有效的镜像三联码

题解

这道题的关键是理解"镜像三联码"的构造规律。

设一个数字的十进制表示为字符串 ，长度为 （如果长度不能被3整除，直接不可能构成镜像三联码）。

将 等分为三段：，其中每段长度都是 。

根据题目要求：

1. 是回文串（长度为 ）
2. 是回文串（长度为 ）

设 ，，。

对于 是回文串，意味着 对于 是回文串，意味着

因此：

这意味着 与 相同，而 是 的反转。

所以一个镜像三联码的结构完全由其前 位 决定：

构造约束：

• 的第一位不能为 0（否则原数有前导零）

对于固定的段长度 ， 可以选择的范围是 ，共有 种选择。

因此长度为 的镜像三联码个数恰好是 。

由于 ，最大总长度是 18，即 。所有可能的镜像三联码总数不超过：

因此可以预处理出所有的镜像三联码，存入数组并排序。对每个查询，使用二分查找统计落在区间 内的个数。

时间复杂度：

• 预处理：（生成并排序）