C. New Year and Permutation

题意：序列是一个数组，由n个从1到n不同的数字组成，我们可以从序列b中得到一个子序列a，子序列的两个端点为[l，r]，是连续的，对于一个序列，其中的数字为p1，p2，p3，p4....，pn，如果给定一个端点[l, r]，如果\(\max\{p_l, p_{l+1}, \dots, p_r\} - \min\{p_l, p_{l+1}, \dots, p_r\} = r - l\)，那么我们称之为\(framed segments\)，我们定义一个序列p的幸福度为这个序列中\(framed segments\)的个数。给定两个整数n，m，计算长度为n的序列中\(framed segments\)的个数，然后对这个个数对m取余。

分析：这是一道组合数学题，我们可以巧妙地去枚举长度为n的数列，我们可以换个角度，不去枚举所有的生成排列，我们可以去枚举子序列，假设我们枚举了一个长度为len的子序列，这个序列中的最大值和最小值相减为这个子序列的长度，这个子序列中数字的全排列为len的阶乘，然后这个子序列的最大值和最小值在整个长度为n的序列中，有n - len + 1种选法，然后我们再对这个长度为n的数列中的剩下数字全排列，那么就有!(n - len + 1)种排列方式，那么我们就可以得到整个公式为\((n - i + 1) * frac[i] * (frac[n - i + 1])\)，对于阶乘，我们可以预处理出来，如果还是不懂，可以画下图，很快就明白了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
using LL = long long;
const int N = 250005;

LL frac[N];
int main()
{
    LL n, mod;
    scanf("%lld%lld", &n, &mod);

    frac[0] = 1;
    //0的阶乘 == 1
    for (int i = 1; i <= n; ++i)
        frac[i] = frac[i - 1] * i % mod;

    //剩余数n - i + 1的顺序
    LL ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        ans += (n - i + 1) * (frac[i] * frac[n - i + 1] % mod);
        ans %= mod;
    }

    cout << ans << endl;

    return 0;
}

C. New Year and Permutation

原文：https://www.cnblogs.com/pixel-Teee/p/12213734.html