[Good Bye 2018 D] New Year and the Permutation Concatenation（组合数学）

题目链接：https://codeforces.com/contest/1091/problem/D
题意：给一个由字典序顺序的全排列拼接成的数列，问其中有多少个长度为 $n$ 的连续子序列和为 $\dfrac{n(n+1)}{2}$

长度为 $n$ 的子序列和为 $\dfrac{n(n+1)}{2}$ 的意思就是说有多少个连续子序列是 $1$ 到 $n$ 的全排列。

这题场上是找规律拆分贡献递推+OEIS过的，早上重新按照拆分贡献再推了一下，发现其实完全不需要OEIS。

首先分析一下答案的贡献：

$n!$ 个原始排列的贡献。
两个排列相交的贡献。

第1部分非常容易，答案就是 $n!$ . 关键是第二个部分。

例如 $n=4$ ，手写几个看看规律（我写了 $(n-1)!+1=3!+1$ 个排列的串，多1个是为了说明规律，后面的结果以此类推）：

1234 1243 1324 1342 1423 1432 2134…

我们从第一个排列的第2个数字开始，于是可能的排列是：

1 2341 2431 3241 3421 4231 4322 134 …

我们发现，两个相邻的排列是从第一个排列的第2个数字开始数的时候（也就是数到第二个排列的第1个数），前面 $3!-1=5$ 对排列都是合法的，当1432遇到2134时则构造不出来（是4322）。

由于开头的数字可以是1、2、3、4任意一个，每一个数字的作为开头都有5个答案，于是这种构造对答案的贡献是 $5\times4=20$ .

同理，从第一个排列的第3个数字开始，可能的排列是：

12 3412 4313 2413 4214 2314 3221 34 …

从第4个数字开始就都不行了。

于是我们发现：每次选第一个数列的第 $k+1$ 个数字作为开头时，必须保证这两个数列的第 $k$ 个数字相同，这样才能保证构造出来的是一个排列，这样的k可以从1取到n-1。

找到了这样的贡献分布，可是计算上是有点麻烦的。正难则反，考虑找到两个数列的第 $k-1$ 个数字不同的排列对数。我们发现 $k=1$ 时候，1、2、3、4开头合法的各5个，那么一共有20个； $k=2$ 时，合法的有12个。以此类推，我们发现，针对每一个 $k$ ，对于答案的贡献是 $n!-n(n-1)..(n-k-1)$ ，于是总的贡献就是：

$n\times n!-\sum_{k=1}^{n-1}\dfrac{n!}{k!}$

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
using PLL = pair<LL,LL>;
const int maxn = 1010000;
const LL mod = 998244353;
LL n;
LL a[maxn], f[maxn];

LL exgcd(LL a, LL b, LL &x, LL &y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  else {
    LL ret = exgcd(b, a%b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return ret;
  }
}

LL inv(LL a) {
  LL x, y;
  exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}

signed main() {
  // freopen("in", "r", stdin);
  scanf("%lld",&n);
  f[0] = f[1] = 1;
  for(int i = 2; i < maxn; i++) {
    f[i] = i * f[i-1] % mod;
  }
  LL ret = n * f[n] % mod;
  for(int i = 1; i < n; i++) {
    LL tmp = f[n] * inv(f[i]) % mod;
    ret -= tmp; ret += mod; ret %= mod;
  }
  printf("%lld\n", ret);
  return 0;
}