AT_abc431_f题解

· · 题解

不重要的碎碎念

为数不多的几次场切F题，虽然这题显然没有F题难度，但是还是很有纪念意义的

简要题目

给你一个长度为 N 的整数序列 A 和一个正整数 D 。
求通过重新排列 A 得到的满足以下条件的整数序列 B 的个数：

结果对 998244353 取模。

其中 2\leq N\leq 2\times 10^5。

分析

首先好想到数组的一开始的顺序对结果并无影响，不妨将原数组先排好序，接着从小往大往序列里加数。

我们假设现在已经排好序，加完前 i-1 个数了，思考能够把第 i 个数放在哪些位置。

其实就是两个条件（我们假设当前数为 x，放在了 a 的后面以及 b 的前面）：

当且仅当上述两个条件成立时，x 才能放在 a 与 b 之间。

由于我们是从小往大排序的，因此第一个条件一定成立。对于第二个条件，我们只需要维护在 A_i 前面的一共有多少个数 A_j 使得 A_i-D\leq A_j 成立，我们记为 Pre_i，这个其实是一段区间，左端点是单调的，因此可以双指针预处理。

不要忘了，x 其实也可以加在最后的位置，因此在第 i 位的答案要乘以 Pre_i+1。

最后还有一点细节，就是关于重复的问题，其实只需要处理一下每个数出现了多少次，写个阶乘的逆元处理一下就好啦。

放代码时间。

#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)
#define fs first
#define sc second
#define pii pair<int,int>
#define pb push_back
using namespace std;
const int N=2e5+5,mod=998244353;
int n,d,a[N],pre[N],fac[N],inv[N];
int quickPow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)
    {
        fac[i]=fac[i-1]*i%mod;
    }
    inv[N-1]=quickPow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--)
    {
        inv[i]=inv[i+1]*(i+1)%mod;
    }
}
void solve()
{
    init();
    cin>>n>>d;
    For(i,1,n)cin>>a[i];
    sort(a+1,a+n+1);
    int now=0;
    a[0]=-0x3f3f3f3f;
    For(i,1,n)
    {
        while(now<i&&a[i]>a[now]+d)now++;
        pre[i]=i-now;
        // cout<<i<<' '<<a[i]<<' '<<pre[i]<<'\n';
    }
    // cout<<'\n';
    int ans=1;
    now=1;
    // cout<<inv[1]<<'\n';
    For(i,2,n)
    {
        if(a[i]!=a[i-1])
        {
            // cout<<now<<' '<<inv[now]<<' '<<ans<<'\n';
            ans=ans*inv[now]%mod;
            now=0;
        }
        now++;
    }
    ans=ans*inv[now]%mod;
    For(i,1,n)
        ans=ans*(pre[i]+1)%mod;
    cout<<ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}

后记

什么？这竟然是原。