题解：AT_arc148_e [ARC148E] ≥ K
luobotianle
·
·
题解
求合法序列数量，考虑将所有数一个个插入；
由于需要维护可放的位置，所以我们要尽可能的让一个数被插入时，要么之后的数都能放在它的左右两边，要么都不能；
具体地，先对 a 数组排序，随后我们使用两个指针 l，r，先固定 l，不断令 r \gets r-1 并插入 a_r 直到 a_l+a_r<k，随后插入 a_l 并令 $l \gets l+1
我们发现，当 $a_r$ 被插入序列中时，它的左右两边**一定可以放数**；
- 因为当 $a_r$ 被插入时 $a_l+a_r \ge k$，而接下来的 $a_l$ 会变大，所以之后要插入的数都可以放在 $a_r$ 两侧。
而当 $a_l$ 被插入时，它的左右两边**一定不能放数**；
- 当 $a_l$ 被插入时 $a_l+a_r<k$，而接下来 $a_r$ 会变小，所以之后要插入的数都不能放在 $a_l$ 两侧。
所以，每插入一个 $a_r$，会使可用位置增加 $1$；而每插入一个 $a_l$，会使可用位置减少 $1$，开一个 $tot$ 维护，每插入一个数时把当前的 $tot$ 乘到答案里即可。
注意此时我们将相同元素当成了不同元素计算，所以最后要除以每种数的个数的阶乘以消除影响。
```cpp
#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=998244353;
int n,k,a[N];
int fac[N],inv[N];
int qp(ll a,int b,int mod=mod){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}
map<int,int> cnt;
int ans=1;
int tot=1;
main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;
inv[n]=qp(fac[n],mod-2);
for(int i=n-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++){
cin>>a[i];
cnt[a[i]]++;
}
sort(a+1,a+1+n);
int l=1,r=n;
while(l<=r){
ans=ans*tot%mod;
if(a[l]+a[r]>=k)r--,tot++;
else l++,tot--;
}
int tot=unique(a+1,a+1+n)-(a+1);
for(int i=1;i<=tot;i++){
int tt=cnt[a[i]];
ans=ans*inv[tt]%mod;
}
cout<<ans;
return 0;
}
```