题解：AT_abc431_f [ABC431F] Almost Sorted 2

· · 题解

题目传送门

思路

双倍经验

唯一的区别就是本题当 A_i 相同时看做 1 个答案。而另一题中原来 A_i 值相同但位置不同被看做多个答案。

题目要求 O(n) 或 O(n \log n)。由于 N 没到 10^6，猜测为 O(n \log n)。

发现可以用双指针做。直接排序（注意是降序）。我们对于每一个 r，找到最远的 l(l \ge r)，使其满足条件，即 A_l-d \le A_r。该部分答案即为 (r-l+1)。答案求累乘。乘法原理证明。由于 l 单调不降，则时间复杂度瓶颈在排序的 O(n \log n)。这样就搞定了双倍经验那题。

然后你的样例一错了……

你发现当 A_i 相同时看做 1 个答案。所以我们要除去每种值出现多的部分。考虑用 \text{map} 记录 A_i 元素出现次数。则不难发现，对于值 x，你需要除以掉 \displaystyle\prod_{i=1}^{mp_x} i。考虑费马小定理求逆元。

即原本答案为 ans，则现在的答案就是 \frac{ans}{\displaystyle\prod_{x\in A}\displaystyle\prod_{i=1}^{mp_x} i}。

总时间复杂度为 O(n \log n)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
const int mod=998244353;
int n,d,a[N],ans=1;
map <int,int> mp;
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }return ans;
}
signed main(){
    scanf("%lld%lld",&n,&d);
    for(int i=1;i<=n;i++) scanf("%lld",a+i),mp[a[i]]++;
    sort(a+1,a+n+1,greater<int>());
    for(int l=1,r=1;r<=n;r++){
        while(a[l]-d>a[r]) l++;
        ans=ans*(r-l+1)%mod;
    }
    for(auto i:mp)
        for(int j=1;j<=i.second;j++) ans=ans*qpow(j,mod-2)%mod;
    printf("%lld",ans);
    return 0;
}

撒花！