Soluton one： 解题思路：
打表可发现：
3——————9
4——————56
5——————395
6——————3084
（因为连起来的排列组合的sum一定是n*(n-1)/2,所以）
3——————9=3!+3=3!+1*3
4——————56=4!+32=4!+4*8
5——————395=5!+275=5!+5*55
6——————3084=6!+2364=6!+6*394
n-----------------S = n! + n * p[n-1] -1;
#include<bits/stdc++.h> using namespace std; //string s[210]; //bool vis[110]; typedef long long ll; const int maxn = 3e6 + 5; const int mod = 998244353; ll p[maxn]; int main(){ ll n ; cin >> n; ll fac; p[1] = 1; p[2] = 2; p[3] = 9; fac = 6; for(int i = 4; i <= n; i++){ fac = fac * i %mod; p[i] = (((p[i-1] - 1)%mod*i) % mod + fac) %mod; } cout << p[n] << endl; return 0; }Solution two: 官方题解 题意：给n!个n的排列，按字典序从小到大连成一条序列，例如3的情况为：[1,2,3, 1,3,2, 2,1,3 ,2,3,1 ,3,1,2 ,3,2,1],问其中长度为n，且和为sum=n*(n+1)/2的序列有多少个？
思路（官方题解）：我们考虑一下next_perumation函数产生字典序递增的全排列的过程：
假设某一个序列长度为n，最长的递减的后缀长度k，那么它的下一个排列是这样产生的：选取序列第n-k个数，与后k个数中比第n - k个数大的最小的数交换，然后将后k个数按从小到大排序。
例如序列1,2,5,4,3的下一个排列为1,3,2,4,5。我们观察发现：这种时候1,2,(5,4,3,1,3,)2,4,5不满足和为sum了，因为在产生下一个排列的过程中，第n-k个位置的数被替换了。
也就是说，假设一个序列存在长度为k的递减后缀，那么这个后缀不能产生一个长度为sum的序列。例如，1,2,(5,4,3,1,3,)2,4,5不行，但是1,(2,5,4,3,1,)3,2,4,5可以。
所以，我们的任务是找出每个长度为k的递减后缀有多少个？应该为C(n,n-k)*(n-k)!=A(n,n-k)=n!/k!个。因为只要选了前面n-k个数，后面长度为k的递减的序列是固定的，所以我们只需要选n-k个数全排列就行了。
我们可以得到最终的答案了：一共有n*n!-(n-1)个序列，要减去( ∑(k from 1 to n-1) n!/k! )- (n-1)个。
为什么要减去n-1个呢？我们来看最后一个排列（假设n为5）5,4,3,2,1 。5之后的序列不存在，所以要从总的序列数中减去。而这(n-1)个不存在的序列恰好会被判定为不满足题意，也应该减去。
所以总的来说，答案应该是：(所有的序列-不存在的序列）-（不满足的序列-不存在的序列）。我们可以把答案写的更优雅一点：ans=n*n!-∑(k from 1 to n-1) n!/k!。
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<cstring> #include<map> #include<set> #include<bitset> #include<queue> #include<vector> #include<stack> #define INF 0x3f3f3f3f #define pii pair<int,int> #define LL long long #define fi first #define se second #define ls(x) (x<<1) #define rs(x) ((x<<1)+1) #define lowbit(x) (x&(-x)) using namespace std; const int maxn=1000010; const LL mod=998244353; LL s[maxn],f[maxn];//s[k]是n!/k! int main(){ LL n; scanf("%lld",&n); f[0]=1,s[n]=1; for(LL i=1;i<=n;i++){ f[i]=(f[i-1]*i)%mod; } for(LL i=n-1;i>=1;i--){ s[i]=(s[i+1]*(i+1))%mod; } LL ans=(n*(f[n]))%mod; for(LL i=1;i<=n-1;i++){ ans=(ans-s[i]+mod)%mod; } cout<<ans<<endl; }Solution three： 对于合理的序列有两种情况，第一种是就是排列的，第二种就是前面k个与后面的n−k的一块组成。
对于第一种情况，答案只要n个，所以我们只考虑第二种情况。
当n=3时，n×n!=3!×3=18 而直接生成的序列为[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] 而我们思考next_permutatin是怎么判断下一个排列的，假设某一个序列长度为n，最长的递减的后缀长度k，那么它的下一个排列是这样产生的：那么它的下一个排列是这样产生的：与后k个数中比整个序列的第n−k个数大且最小的那个交换，然后将后k个数按从小到大排序。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define int long long #define mod 998244353 using namespace std; inline int read() { int f=1,ans=0;char c; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();} return ans*f; } const int N=2000001; int ans,n,fac[N],f[N]; signed main(){ n=read();fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i,fac[i]%=mod; f[n]=1; for(int i=n-1;i>=1;i--) f[i]=f[i+1]*(i+1),f[i]%=mod; ans=n*fac[n]; for(int i=1;i<n;i++) ans=((ans-f[i])%mod+mod)%mod; printf("%d\n",ans); }