-
f[n]表示n的全排列的价值数总和,
-
思路:由f[3]–>f[4] 从而由f[n-1]–>f[n]
对于全排列的其中一个序列 1 2 3
4 1 2 3 在第一个数前面插入,则此时价值为 123序列的价值
1 4 2 3 在第一个数后面插入,则此时价值为 1+123序列价值
1 2 4 3 在第二个数后面插入,价值为:2+123序列价值
1 2 3 4 在第三个数后面插入,价值为3+123序列价值
所以从一个序列推广到6个序列(因为3的全排列的个数为:3!)
所以 推广到所有3的所有全排列序列:
在第一个数前面插入,价值为: (序列1+序列2+。。序列6)=f[3]
在第一个数后面插入,价值为: (1+序列1)+(1+序列2)+.。(1+序列6)= 3!1+f[3]
在第二个数后面插入,价值为: (2+序列1)+(2+序列2)+.。(2+序列6)= 3!2+f[3]
在第三个数后面插入,价值为: (3+序列1)+(3+序列2)+.。(3+序列6)= 3!3+f[3]
总价值:f[4]=f[3]+3!1+f[3]+3!2+f[3]+3!3+f[3]=4f[3]+3!(1+2+3)
所以推广到n:f[n]=nf[n-1]+(n-1)!n(n-1)/2
#include<iostream>
using namespace std;
typedef long long ll;
int n;
#define N 1000005
const ll mod=998244353;
ll f[N],fact[N],sum[N];
int main(){
cin>>n;
fact[0]=1;
for(int i=1;i<=n;i++){
f[i]=(i*f[i-1]+fact[i-1]*sum[i-1])%mod;
fact[i]=i*fact[i-1]%mod;
sum[i]=(i+sum[i-1])%mod;
}
cout<<f[n]<<endl;
return 0;
}