[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。

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

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

第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!}
$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#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;
}