Codeforces 1091D New Year and the Permutation Concatenation
https://codeforces.com/contest/1091/problem/D
题目：
Let n be an integer. Consider all permutations on integers 1 to n in lexicographic order, and concatenate them into one big sequence p. For example, if n=3, then p=[1,2,3,1,3,2,2,1,3,2,3,1,3,1,2,3,2,1]. The length of this sequence will be n⋅n!n⋅n!.
Let 1≤i≤j≤n⋅n!be a pair of indices. We call the sequence (pi,pi+1,…,pj−1,pj) a subarray of pp. Its length is defined as the number of its elements, i.e., j−i+1. Its sum is the sum of all its elements, i.e., ∑jk=ipk.
You are given n. Find the number of subarrays of p of length n having sum n(n+1)/2. Since this number may be large, output it modulo 998244353 (a prime number).
Input
The only line contains one integer n (1≤n≤106), as described in the problem statement.
Output
Output a single integer — the number of subarrays of length nn having sum n(n+1)/2, modulo 998244353.
Examples
Input1
3
Output1
9
Input2
4
Output2
56
Input3
10
Output3
30052700
Note
In the first sample, there are 16 subarrays of length 3. In order of appearance, they are:
[1,2,3], [2,3,1], [3,1,3], [1,3,2], [3,2,2] [2,2,1], [2,1,3], [1,3,2], [3,2,3], [2,3,1], [3,1,3], [1,3,1]， [3,1,2], [1,2,3], [2,3,2], [3,2,1].
Their sums are 6, 6, 7, 6, 7, 5, 6, 6, 8, 6, 7, 5, 6, 6, 7, 6. As n(n+1)/2=6, the answer is 9.
分析：
这道题题意挺明确的，输入一个n，然后把长度为n，初始值为1的连续递增的数列进行全排列然后排在一块，再找其中连续的n个数，要求这n个数必须是1-n。
题意就是这样那么就分析：
暴力，呵呵呵呵，祝你好运
看到只输入一个数n，第一反应就是oeis
无果，遂自寻规律
此处应该有规律
1~10是
1 2 9 56 395 3084 26621 253280 2642391 30052700
当然这个在一开始做的时候是绝对绝对不知道的
于是手推
推大概n=5的时候395还没有太大的问题，分成第一个数字是12345可以分成五份，然后用全排列打个小程序，看看规律
首先一个很显然的事实：
当全排列第一个数字是1和全排列第一个数字是2的凑在一块，是肯定无法实现1-n的排列的
所以我们可以把整体分为n份，此为第一个结论
然后分析每一块
先以n=3开始
全排列是
123132
显然123 132 是两个，也就是组成这个大数列P的是肯定必须都满足条件
然后就是231，此为第一个全排列的第二个数开始，这是重中之重
第二个全排列的第二个数后面没有后继的数，遂作罢
当n=4时，
1234 1243 1324 1342 1423 1432
首先显然的是6个
其次就是每个全排列的第二个数和后面的n-1个数组成的都是成立的
这些是5个
然后每个全排列的第三个数开始的长度为n的数列成立的是3个
这时候可能会有一丝丝思路，但不明确
当n=5的时候
写出来有点小多啊。。。。
那就用程序跑
截取我输出的结果
51234
51243
51324
51342
51423
51432
52134
52143
52314
52341
52413
52431
53124
53142
首先的24个是跑不了
然后接下来的23也跑不了
再往下看，，就有些神奇了
此时应该关注每个全排列的第三个数
第三个数和第四第五个数，用竖着看的方式，会发现当前两个数固定，就是后面在进行全排列！（废话这是全排列的性质）
那么我们可以分析出来这24个中，5个成立的，1个不成立的，5个成立的，1个不成立的
咦居然有周期
试试第四个数
1,1,1,1,1
也就是成立和不成立交叉着
那么和第四个数相匹配，那是什么？
23+1 = 24
5+1 = 6
1+1 = 2
这不就是阶乘吗！
然后再用心钻研那么一点点
((n-1)!+(n-1)!*((n-2)!-1)/(n-2)!+(n-1)!*((n-3)!-1)/(n-3)!···)*n
讲真这里还不如自己手写一下然后看代码
对了除法取模要用逆元
这道题你要说不会做以后遇到怎么办，我只能说多练数学题，培养对数学的感觉，就是这样
AC代码
1 #include <stdio.h>
2 #include <math.h>
3 #include <string.h>
4 #include <algorithm>
5 #include <iostream>
6 #include <string>
7 #include <time.h>
8 #include <queue>
9 #include <string.h>
10 #define sf scanf
11 #define pf printf
12 #define lf double
13 #define ll long long
14 #define p123 printf("123\n");
15 #define pn printf("\n");
16 #define pk printf(" ");
17 #define p(n) printf("%d",n);
18 #define pln(n) printf("%d\n",n);
19 #define s(n) scanf("%d",&n);
20 #define ss(n) scanf("%s",n);
21 #define ps(n) printf("%s",n);
22 #define sld(n) scanf("%lld",&n);
23 #define pld(n) printf("%lld",n);
24 #define slf(n) scanf("%lf",&n);
25 #define plf(n) printf("%lf",n);
26 #define sc(n) scanf("%c",&n);
27 #define pc(n) printf("%c",n);
28 #define gc getchar();
29 #define re(n,a) memset(n,a,sizeof(n));
30 #define len(a) strlen(a)
31 #define LL long long
32 #define eps 1e-6
33 using namespace std;
34 const ll mod = 998244353;
35 ll pow_quick(ll a,ll b){
36 ll r = 1,base = a;
37 while(b){
38 if(b & 1){
39 r *= base;
40 r %= mod;
41 }
42 base *= base;
43 base %= mod;
44 b >>= 1;
45 }
46 return r;
47 }
48
49 ll a[1000050];
50 int main() {
51 ll n;
52 sld(n)
53 if(n == 1){
54 p(1) pn return 0;
55 }
56 a[1] = 1ll;
57 for(ll i = 2; i <= n; i ++){
58 a[i] = a[i-1]*i;
59 a[i] %= mod;
60 }
61 ll sum = a[n-1];
62 //pld(sum) pn
63 for(ll i = 3; i <= n; i ++){
64 ll x = (a[n-1]*pow_quick(a[i-1],mod-2))%mod;
65 x *= a[i-1]-1;
66 x %=mod;
67 sum += x;
68 sum %= mod;
69 }
70 pld((sum*(n))%mod) pn
71 return 0;
72 }
代码链接：https://codeforces.com/contest/1091/submission/47758982
