【数学】【CF1091D】 New Year and the Permutation Concatenation

蔚落 2021-09-29 03:18 215阅读 0赞

## Description ##

给定一个数 \$n\$，将所有 \$1~\\sim~n\$ 的排列按照字典序放到一个序列中，求有多少长度为 \$n\$ 的子序列 \$p\_i~p\_\{i+1\}~\\dots~p\_\{i + n - 1\}\$ 满足 \$\\sum\_\{u = i\}^\{i + n - 1\}~p\_u~=~\\frac\{n~\\times~(n - 1)\}\{2\}\$ 答案对 \$998244353\$ 取模

## Input ##

一行一个整数代表 \$n\$

## Output ##

一行一个整数代表答案对 \$998244353\$ 取模的结果

## Hint ##

\$1~\\leq~n~\\leq~10^6\$

## Solution ##

做法有很多呐……

对于一个合法的序列，显然其中 \$1~\\sim~n\$ 每个元素都出现了一次。可以使用反证法或按照 \$n\$ 进行数学归纳证明

那么对于一个合法的序列 \$q\$，一共只有两种情况：

> 1、它是由一段完整的排列构成的
> 
> 2、它是由前面一段排列的后 \$k\$ 位和后面一段排列的前 \$n - k\$ 位拼成的。

情况一显然有 \$n!\$ 种，于是我们只考虑情况二的答案

考虑求 next\_permutation 的算法：找出原排列中最长的单调降序后缀，记长度为 \$k\$，然后在后缀中找最小的大于原排列第 \$(n - k - 1)\$ 位的值，将这两个位置交换。然后将新的后缀按照升序排序（因为原先是降序的，所以这个操作等价于进行reverse）

考虑两个相邻的排列，在前面排列中选 \$k\$ 个，后面选 \$n - k\$ 的情况，若这种情况合法，则后面一个排列的前 $n - k $ 位与前面一个排列的前 \$n - k\$ 位是相同的，即这一段没有发生交换。所以他的后缀的长度 \$len\$ 必须满足 \$len~<~k\$。

我们考虑用总方案数减去不合法的方案数：考虑我们对一个排列固定一个选择的数的个数 \$k\$，那么它不合法当且仅当整个后缀是单调降序，前面怎么排无所谓，于是这样的排列共有 \$A\_n^\{n - k\}~=~\\frac\{n!\}\{k!\}\$ 个。这些排列在选后面 \$k\$ 个作为选出子序列的前缀时全部是不合法的。考虑我们这样等价于枚举选择前一个排列的 \$k\$ 的位置，而总共有 \$n~\\times~n!\$ 个数字，于是这样的位置一共有 \$n~\\times~n!\$ 种，即方案有这么多种，减去不合法的方案数即为

\\\[n~\\times~n!~-~\\sum\_\{k = 1\}^\{n - 1\} \\frac\{n!\}\{k!\}\\\]

以上是官方题解

第二种做法与第一种类似，同样依据上面的结论。不过是直接计算方案数。考虑我们如果选择一个排列的后 \$k\$ 个位置，我们设这个排列的后 \$k\$ 位是单调递增的，则对前面选择没影响的是后 \$(n - k)!\$ 次排列，因为这几次排列是将后面 \$k\$ 位从升序排列到降序，对前面没有影响。

考虑直接枚举 \$k\$，前面怎么选无所谓，方案数 \$A\_n^k\$，后面共有 \$(n - k)!\$ 种排列。后面这些排列共有 \$(n - k)! - 1\$ 对，即这么多贡献。于是直接枚举统计答案即可。

以上参考 @[DDOSvoid][] 神仙的做法

第三种做法直接打表找规律，设 \$f\_i\$ 为输入为 \$i\$ 的答案，则

\\\[f\_i~=~(f\_\{i - 1\}~+~(n - 1)!~-~1)~\\times~n\\\]

天知道他们是怎么看出规律的

## Code ##

代码依据官方题解算法写成

#include <cstdio> #ifdef ONLINE_JUDGE #define freopen(a, b, c) #endif #define rg register #define ci const int #define cl const long long typedef long long int ll; namespace IPT { const int L = 1000000; char buf[L], *front=buf, *end=buf; char GetChar() { if (front == end) { end = buf + fread(front = buf, 1, L, stdin); if (front == end) return -1; } return *(front++); } } template <typename T> inline void qr(T &x) { rg char ch = IPT::GetChar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar(); while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar(); if (lst == '-') x = -x; } template <typename T> inline void ReadDb(T &x) { rg char ch = IPT::GetChar(), lst = ' '; while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar(); while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar(); if (ch == '.') { ch = IPT::GetChar(); double base = 1; while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar(); } if (lst == '-') x = -x; } namespace OPT { char buf[120]; } template <typename T> inline void qw(T x, const char aft, const bool pt) { if (x < 0) {x = -x, putchar('-');} rg int top=0; do {OPT::buf[++top] = x % 10 + '0';} while (x /= 10); while (top) putchar(OPT::buf[top--]); if (pt) putchar(aft); } const int maxn = 1000010; const int MOD = 998244353; int n, ans; int inv[maxn], fac[maxn], fac_inv[maxn]; void Get_Inv(ci); int main() { freopen("1.in", "r", stdin); qr(n); Get_Inv(n); fac[1] = 1; for (rg int i = 2; i <= n; ++i) fac[i] = 1ll * fac[i - 1] * i % MOD; ans = 1ll * n * fac[n] % MOD; for (rg int i = 1; i < n; ++i) { ans = (ans - 1ll * fac[n] * fac_inv[i] % MOD) % MOD; } qw((ans + MOD) % MOD, '\n', true); return 0; } void Get_Inv(ci x) { inv[1] = 1;fac_inv[1] = 1; for (rg int i = 2; i <= x; ++i) fac_inv[i] = 1ll * fac_inv[i - 1] * (inv[i] = (1ll * - (MOD / i) * inv[MOD % i]) % MOD) % MOD; }

转载于:https://www.cnblogs.com/yifusuyi/p/10207723.html

[DDOSvoid]: https://www.luogu.org/space/show?uid=34531