Codeforces 1091D
题意：给定$n$，将$[1,n]$的排列按字典序接成$n \cdot n!$长的序列，求序列中有几个长度为$n$的区间和等于$\frac{n(n-1)}{2}$
显然这个区间是一个排列。那么我们可以统计每个排列的贡献。
对于一个合法的区间，他一定是一个排列的结尾接上一个排列的开头。所以可以将组合问题分解
对于一个排列有$n$种分解方法，所以有$n \cdot n!$种方案。
但是有不满足的情况，例如$(4, 2)$, $(1, 3, 5)$是不能接一起的。这样两个排列字典序大小不满足。
观察发现前面的是一个递减序列，所以我们要将这些递减序列构成的都删掉。选出$i$长递减序列有$C^{i}_{n}$种方法，对于每个递减序列他的第二个部分是随便填的，所以最后答案为
$$
n \cdot n! - \sum_{i=0}^n C^i_n \cdot (n-i)!
$$
找规律方法：
1、观察样例解释，发现和等于$\frac{n(n-1)}{2}$的有周期性
2、打表$4$的答案(顺序打印区间和)，发现确实有周期性，并且发现周期为$n!$
3、打表$3,5$的答案，发现答案有递推性
4、发现答案一定是两个数相乘，因为周期是$n!$，选择有$n \cdot n!$种，所以两个数中有一个是$n$
5、对另一个数分析，观察表可以发现$4$的每个周期都在$3$的基础上加上了$(n-1)!$个答案
6、对答案调整分析，上面的还要减一才行
7、写出递推式
$$
f(i)=i \cdot ((i-1)!+f(i-1)-1)
$$
其中$f(1)=1$
1、组合\DP常用方法分解问题
//==========================Head files==========================
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#include<set>
#include<iostream>
#include<map>
#define LL long long
#define db double
#define mp make_pair
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
//==========================Templates==========================
inline int read() {
int x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
inline LL readl() {
LL x = 0, f = 1; char c = getchar();
while(c < '0' || c > '9'){if (c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9'){x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int power(int a, int b) {
int ans = 1;
while (b) {
if(b & 1) ans = ans * a;
b >>= 1; a = a * a;
}
return ans;
}
int power_mod(int a, int b, int mod) {
a %= mod;
int ans = 1;
while (b) {
if(b & 1) ans = (ans * a) % mod;
b >>= 1, a = (a * a) % mod;
}
return ans;
}
LL powerl(LL a, LL b) {
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = ans * a;
b >>= 1ll;a = a * a;
}
return ans;
}
LL power_modl(LL a, LL b, LL mod) {
a %= mod;
LL ans = 1ll;
while (b) {
if(b & 1ll) ans = (ans * a) % mod;
b >>= 1ll, a = (a * a) % mod;
}
return ans;
}
LL gcdl(LL a, LL b) {return b == 0 ? a : gcdl(b, a % b);}
LL abssl(LL a) {return a > 0 ? a : -a;}
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
int abss(int a) {return a > 0 ? a : -a;}
//==========================Main body==========================
#define LD "%I64d"
#define D "%d"
#define pt printf
#define sn scanf
#define pty printf("YES\n")
#define ptn printf("NO\n")
//==========================Code here==========================
const LL MO = 998244353;
LL n, f[1000000 + 5], fac[1000000 + 5];
int main() {
cin >> n;
f[1] = 1ll;
fac[0] = 1ll;
for (LL i = 1ll; i <= n; ++i) fac[i] = (fac[i - 1] * i) % MO;
for (LL i = 2ll; i <= n; ++i) {
f[i] = ((fac[i - 1] + f[i - 1]) % MO - 1ll + MO) % MO;
f[i] = f[i] * i % MO;
}
cout << f[n];
return 0;
}
