京东 · 组合数学 · 算法编程题
京东 组合数学 N ≤ 1e6 时限 1 秒 / 256 MB

题目描述

现在给出近似回文的定义：
· 字符串 S 不是回文； · 字符串 S 仅仅由小写字母 a z 组成。 · 可以通过删除其中一个字符， S 成为回文。 例如 S = "abbda" ,首先 S 仅仅由小写字母构成，并且 S 不是回文，但是可以通过删除字符 d ，使得 S 变为 S' = abba ，现在 S' 为回文。
现在给出字符串的长度 N ，请你计算出该长度下，满足近似回文的字符串有多少个？
由于结果可能很大，请输出对 998244353 取模后的结果。

输入输出

输入描述
输入的第一行包含一个正整数 N ——代表字符串的长度。
1 ≤ N ≤ 10^6
输出描述
一行中输出在长度为 N 的字符串下满足近似回文的字符串有多少个？结果对 998244353 取模。

样例共 2 组

样例 1 · 26*26-26=650
输入
2
输出
650
样例 2
输入
2022
输出
500136964

算法解析依据充分

考点：组合数学 · 快速幂 · 数论

数据规模 N ≤ 1e6 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：N ≤ 1e6
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：组合数学

用计数原理（加法/乘法原理）与组合数公式统计方案数。

思路框架（组合数学 通法 · 非本题专属）

  1. 判断是分类计数（相加）还是分步计数（相乘）。
  2. 识别是否重复/是否有序，决定用排列 A(n,m) 还是组合 C(n,m)。
  3. 组合数递推 C[i][j] = C[i-1][j-1] + C[i-1][j]，或预处理阶乘与逆元。
  4. 答案通常要求对 1e9+7 取模。

实现要点：阶乘预处理 + 费马小定理求逆元可以在 O(1) 内算任意组合数。

复杂度：时间 O(n) 预处理 / O(1) 查询 ｜ 空间 O(n)

该范式的通法易错点

  • 把排列和组合搞混。
  • 取模意义下直接做除法（应乘逆元）。
  • 方案数溢出未取模。

对照本题

  • 数据规模 N ≤ 1e6，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。

样例解读

样例 1：输入 2 → 输出 650

26*26-26=650

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2024年春招-京东-技术通用岗位-第四批笔试。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解