CF1248C-New Year and Permutation

题目大意：问长度为n的所有排列能找到多少个这样的子段：子段最大元素与最小元素的差等于子段的长度。

不难想到，满足条件的子段中的所有元素都是连续的，即1,2,3,4满足条件，1,2,4,5不满足条件。长度为len的连续子段的最大的元素可能为n,n-1,n-2,...,n-len+1，共n-len+1种可能；最大元素相同的子段的内部有$A_{len}^{len}$种，即$len!$种排列方法；这些排好了的子段又在不同的全排列中，在确定这些子段之后，还要将它们视为整体，与整个序列剩下的元素全排列，共$A_{n-len+1}^{n-len+1}$，即$(n-len+1)!$种可能。长度为len的满足条件的子段的个数$res_{len}$就为

$(n-len+1) \times len! \times(n-len+1)!$

答案需要将所有长度的满足条件的子段的个数加起来，即$\sum_{i=1}^{n}res_{i}$，也就是

$\sum_{i=1}^{n}(n-i+1) \times i! \times(n-i+1)!$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#include <bits/stdc++.h>
using namespace std;
long long jc[250005];
int main()
{
    long long n, res = 0, mod, i;
    cin >> n >> mod;
    jc[0] = jc[1] = 1;
    for (i = 2; i <= n; i++)
        jc[i] = jc[i - 1] * i % mod;
    for (i = 1; i <= n; i++)
        res = (res + ((n - i + 1) * jc[i] % mod) * jc[n - i + 1] % mod) % mod;
    cout << res;
    return 0;
}