CF1462E2 相似数组

标签：序列   tar   turn   href   inverse   ++   blank   之间   mamicode   

1 CF1462E2 相似数组

• 题目链接：http://codeforces.com/problemset/problem/1462/E2

2 题目描述

给出一个长度为 \(n\) 的数组 \(a\) 由从 \(1\) 到 \(??\) 的整数构成。数组可能包含重复项(即有些元素可以相等)。
找出\(??\)个元素的数组，使数组中的最大值与最小值相差不超过 \(??\)。也就是说，你需要找到 \(??\) 指数的数组 \(??_1?_2<...>, 这样使得

\(max(\)\(??_??\)\(_1\)\(,\)\(??_??\)\(_2\)\(,...,\)\(??_??\)\(_??\)\()\)-\(min(\)\(??_??\)\(_1\)\(,\)\(??_??\)\(_2\)\(,...,\)\(??_??\)\(_??\)\()≤??\)。

例如，如果 \(??=4,??=3,k=2,??=[1,2,4,3]\)，那么有两个这样的数组 \((??=1,??=2,??=4\) 和 \(i=2,j=3,z=4)\)。如果 \(??=4,??=2,??=1,??=[1,1,1,1]\)，那么所有六种可能的配对都是可以的。

3 解题思路

这道题的难点主要不在找到哪些数满足，而是计算方案数。

首先我们发现，这道题中的方案数与序列的顺序无关，我们就可以先对序列进行排序。然后对于每一个数 \(x\)，我们在其右端找到第一个大于 \(x + k\) 的数，这里我们可以用二分解决。那么在这个数和 \(x\) 中的数随便选取 \(m\) 个数都一定满足条件。虽然我们这么说，但是我们不能直接将 \(C_{len}^m\)（\(len\) 表第一个大于 \(x+k\) 的数的坐标与 \(x\) 的坐标的差，也就是任意选取数都满足条件的这一区间长度）累计到答案中。这是因为在计算下一个数时会有一部分情况与当前情况重合。因此我们假定我们必须选取 \(x\)，这样就不会出现重复或者遗漏的情况。这样当前区间的方案数就是\(C_{len-1}^{m-1}\)。

接下来，我们开始研究 \(C_{len-1}^{m-1}\) 的值如何计算。这道题的 \(m\) 可以到 \(100\)，\(len\) 的理论值可以到 \(2e5\)。也就是说，直接用阶乘计算肯定不行。这道题中给出了模数 \(10^9 + 7\)。但是对于除法，\(\dfrac{x}{y} \mod p \ne \dfrac{x \mod p}{y \mod p}\)。这里，我们可以用求出 \(m !\) 的逆元（\(m!‘\)）。这里有个问题：\(m!\) 还是太大了，可能必须需要取模。这里我们就要引入一个性质：\((pq)‘ = p‘ * q‘\) 。而由于 \(m\) 最大也就是 \(100\)，分开计算 \(m,m-1,...,1\) 的逆元可行。逆元的具体计算，可以用费马小定理 \(a‘ = a^{p-2}\)（\(p\) 为模数）。

我们发现，尽管我们可以如此计算出 \(m!\) 的逆元，但是对于 \(len * (len-1)*(len-2)...(len-m+1)\)，我们的计算仍然可能超时。这里我们可以预处理出所有 \(1\)~\(2e5\) 之间的数的逆元，存在\(in\)数组里。然后用一个数组\(ti\)来存储
\(len\)为 不同值时的情况。我们发现，当\(len = m\)的时候，\(ti[len] = m!\)。而后面\(len\)每增加\(1\)，都要除以\(len - m\)，也就是上一个\(len\)的\((len - m + 1)\)，并且乘上\(len\)，而这里除的\(len - m\)的逆元已经被求出，只需将 \(ti[len]\)乘 以这个数即可。形象地说，\(ti[len] = (((ti[len-1] * in[len]) \% (10^9+7)) * len) \% (10^9+7)\)。

至此，我们已经将计算 \(C_{len - 1} ^ {m-1}\) 中遇到的所有困难解决了，剩下就是累积进答案并且输出了。时间复杂度：\(O(T*n*\log_2n)\)，完全足够。剩下就是别忘了开 \(long\space long\)，毕竟本题的 \(n\) 高达 \(2e5\)，在计算 \(ti\) 数组的时候可能会爆 \(int\)。

4 代码（空格警告）：

#include 
#include 
#include 
using namespace std;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int T, n, m, k, l, r, mid, pos, len;
long long num, im;
int a[N];
long long ti[N], in[N];
long long inverse(long long a)
{
    long long b = mod - 2;
    long long ans = 1;
    while (b)
    {
        if (b & 1) ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}
int main()
{
    for (int i = 1; i 

欢迎关注我的公众号：智子笔记

CF1462E2 相似数组

标签：序列   tar   turn   href   inverse   ++   blank   之间   mamicode   

原文地址：https://www.cnblogs.com/david24/p/14375455.html