题解:CodeForces Hello 2020 C
KONGJUNE / / ACM / 阅读量

题目传送门:🚪

Recall that the permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

A sequence $a$ is a subsegment of a sequence $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. We will denote the subsegments as $[l,r]$, where $l$, $r$ are two integers with $1≤l≤r≤n$. This indicates the subsegment where $l−1$elements from the beginning and $n−r$ elements from the end are deleted from the sequence.

For a permutation $p_1,p_2,…,p_n$, we define a framed segment as a subsegment $[l,r]$ where $\max{p_l,p_{l+1},…,p_r}−\min{p_l,p_{l+1},…,p_r}=r−l$. For example, for the permutation $(6,7,1,8,5,3,2,4)$ some of its framed segments are: $[1,2]$,$[5,8]$,$[6,7]$,$[3,3]$,$[8,8]$. In particular, a subsegment $[i,i]$ is always a framed segments for any $i$ between $1$ and $n$, inclusive.

We define the happiness of a permutation $p$ as the number of pairs $(l,r)$ such that $1≤l≤r≤n$, and $[l,r]$ is a framed segment. For example, the permutation $[3,1,2]$ has happiness $5$: all segments except $[1,2]$ are framed segments.

Given integers $n$ and $m$, Jongwon wants to compute the sum of happiness for all permutations of length $n$, modulo the prime number $m$. Note that there exist $n!$(factorial of $n$) different permutations of length $n$.

Input

The only line contains two integers $n$ and $m$ ($1≤n≤250000$, $108≤m≤109$, $m$ is prime).

Output

Print $r$ $(0≤r<m)$, the sum of happiness for all permutations of length $n$, modulo a prime number $m$.

Examples

Input Output
1 993244853 1
2 993244853 6
3 993244853 32
2019 993244853 923958830
2020 437122297 265355509

Note

For sample input $n=3$, let's consider all permutations of length $3$:

  • $[1,2,3]$, all subsegments are framed segment. Happiness is $6$.
  • $[1,3,2]$, all subsegments except $[1,2]$ are framed segment. Happiness is $5$.
  • $[2,1,3]$, all subsegments except $[2,3]$ are framed segment. Happiness is $5$.
  • $[2,3,1]$, all subsegments except $[2,3]$ are framed segment. Happiness is $5$.
  • $[3,1,2]$, all subsegments except $[1,2]$ are framed segment. Happiness is $5$.
  • $[3,2,1]$, all subsegments are framed segment. Happiness is $6$.

Thus, the sum of happiness is $6+5+5+5+5+6=326$.

这是一道数学题,通过推到出结果的表达式即可。

我们从子序列长度的角度来考虑。

  • 当子序列长度为 $1$ 时,序列的每一个子序列都是符合条件的,而序列的排列数共有 $n!$ 种,故这种情况下,幸福度(happiness)为 $n \cdot n!$。

  • 当子序列长度为 $2$ 时,我们有以下分析:

    序列共有 $n!$ 种,每个序列均有 $n - 1$ 个不同的长度为 $2$ 的子序列。而这些子序列是随机出现的,所以他们成为符合条件的子序列的概率相等。

    至于子序列符合条件的概率,我们现在只考虑长度为 $2$ 的子序列。

    长度为 $2$ 的子序列共有 $A_n^2 = n(n-1)$ 种,其中满足条件的有 $(n - 1) \cdot 2!$ 种,即不考虑顺序的从序列 $1,2,3,\dots,n$ 种连续选择长度为 $2$ 的子序列有 $n - 1$ 种,再考虑每个序列的顺序有 $2!$ 种。所以满足条件的概率为 $\frac{(n-1)\cdot2!}{A_n^2}$ 。

    综上,长度为 $2$ 的子序列的幸福度(happiness)的总和为 $n!(n - 1) \cdot \frac{(n - 1) \cdot 2!}{A_n^2}$。

  • 当子序列长度为 $3$ 时,根据类似的分析,我们得到的幸福度总和为 $n!(n - 2)\cdot\frac{(n - 2)\cdot3!}{A_n^3}$。

根据以上的分析可推知当子序列长度为 $n$ 时,幸福度总和为 $n!(n - i + 1)\cdot\frac{(n - i + 1)\cdot i!}{A_n^i}$,化简后为:$(n-i+1)\cdot i!\cdot (n - i + 1)!$。所以本题目的最终结果为:
$$
\sum_{i =1}^n(n - i + 1)\cdot i ! \cdot(n - i + 1)!
$$
由于 $i!$ 种 $i$ 从小到大变化,而 $(n - i + 1)!$ 中 $n - i + 1$ 从大到小变化,所以我们需要预处理并储存出最大至 $n!$ 的值(注意取模),以减小时间复杂度。

取模运算规则

  • $(a+b) \mod p = (a \mod p + b\mod p)\mod p$

  • $(a-b)\mod p =(a\mod p - b \mod p)\mod p$

  • $(a\times b) \mod p =(a\mod p\times b \mod p) \mod p$

  • $(a ^ b)\mod p = ((a \mod p) ^ b)\mod p$

  • 除法:分子乘以分母的乘法逆元。

    $(a\div b)\mod p = (a\times b^{p - 2} )\mod p$

AC代码:

#include <bits/stdc++.h>
using namespace std;
long long mul[250005];
int main() {
    int n, m;
    cin >> n >> m;
    mul[0] = 1;
    for (int i = 1; i <= n; i++) {
        mul[i] = ((mul[i - 1] % m) * (i % m)) % m;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = (ans + ((((n - i + 1) % m) * ((mul[i] * mul[n - i + 1]) % m)) % m)) % m;
    }
    cout << ans << endl;
}
支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
有 0 篇文章