AT_abc431_f题解

不重要的碎碎念

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

简要题目

给你一个长度为

N

的整数序列

A

和一个正整数

D

。
求通过重新排列

A

得到的满足以下条件的整数序列

B

的个数：

$B_{i+1}≥B_i-D$ 对所有 $i\ (1\leq i\leq N-1)$ 都成立。

结果对 998244353 取模。

其中

2\leq N\leq 2\times 10^5

。

分析

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

我们假设现在已经排好序，加完前

i-1

个数了，思考能够把第

i

个数放在哪些位置。

其实就是两个条件（我们假设当前数为

x

，放在了

a

的后面以及

b

的前面）：

$a-D\leq x$
$x-D\leq b$

当且仅当上述两个条件成立时，

x

才能放在

a

与

b

之间。

由于我们是从小往大排序的，因此第一个条件一定成立。对于第二个条件，我们只需要维护在

A_i

前面的一共有多少个数

A_j

使得

A_i-D\leq A_j

成立，我们记为

Pre_i

，这个其实是一段区间，左端点是单调的，因此可以双指针预处理。

不要忘了，

x

其实也可以加在最后的位置，因此在第

i

位的答案要乘以

Pre_i+1

。

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

放代码时间。

CPP

#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;
}

后记

什么？这竟然是原。

文章操作

不重要的碎碎念

简要题目

分析

后记

相关推荐

评论

AT_abc431_f题解