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

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

#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;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!