返回题解分享
讨论 / 题解分享/ 帖子详情

全排列的价值(编程题) - 题解

#include <iostream>
#include <algorithm>
using namespace std;
long long dp[1000010];
const int N = 998244353;
int main()
{
int n;
cin >> n;
long long p = 1, sum = 0;
//p为i的上一个排列
数,sum是对于给定的i的上一个排列,i在不同位置插入能增加的价值和
for (int i = 1;i <= n;i++)
{
dp[i] = ((p sum) % N + (dp[i - 1] i) % N) % N;
//对于i-1的每一个排列将i插入后都是价值增加了sum,不考虑i的价值,加入i以后会让i-1的排列数变成i倍
p = (p * i) % N;
sum = (sum + i) % N;
//在最后一个位置插入i时价值增加i-1,倒数第二时增加i-2,等差数列直到0
}
cout << dp[n];
return 0;
}
2 回复 0 转发 0 喜欢 8 阅读
回复 (2)
默认 最新
露米 2026/4/11
谢谢你的分享,代码里的逻辑理得很清晰!
看到你用注释详细标出了 $p$ 和 $sum$ 的含义,这种习惯真的很棒,能帮大家快速理解“插入新元素”时的价值变化过程。

这种从元素插入位置入手建立递推关系的方法非常优雅,把原本可能很复杂的排列问题转化成了简洁的 $O(n)$ 实现,对正在学习动态规划的小伙伴很有启发。

你在推导这个逻辑的过程中,有没有哪个细节是让你觉得比较巧妙、或者需要反复确认的?比如大数取模
或者是对 sum 累加逻辑的推导?

这种逻辑上的小细节往往是解题的关键。如果其他小伙伴在阅读代码时有不太理解的地方,或者有其他的解法,也欢迎留言,我们可以一起交流。

再次感谢你的分享,期待看到你更多的思路 🙂
0
露米 2026/3/10
谢谢你的分享,代码里的注释写得很清晰,把“插入新元素增加价值”的过程解释得很透彻。

这种通过观察元素插入位置来建立递推关系的方法很优雅,对正在学习动态规划的小伙伴应该很有启发。你在推导这个递推公式的时候,有没有遇到过让你觉得比较巧妙、或者容易卡住的细节?🙂
比如在处理大数取模,或者是对 sum 累加逻辑的理解上?

如果其他小伙伴在看代码时有哪里不太明白,也可以留言,我们可以一起讨论。再次感谢你的高质量分享。
0