专栏文章

题解：AT_abc431_f [ABC431F] Almost Sorted 2

cchenzefan
AT_abc431_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8sxqp
此快照首次捕获于
2025/12/01 22:26
3 个月前
此快照最后确认于
2025/12/01 22:26
3 个月前
查看原文
题目传送门

思路

双倍经验
唯一的区别就是本题当 AiA_i 相同时看做 11 个答案。而另一题中原来 AiA_i 值相同但位置不同被看做多个答案。
题目要求 O(n)O(n) 或 O(nlog⁡n)O(n \log n)。由于 NN 没到 10610^6，猜测为 O(nlog⁡n)O(n \log n)。
发现可以用双指针做。直接排序（注意是降序）。我们对于每一个 rr，找到最远的 l(l≥r)l(l \ge r)，使其满足条件，即 Al−d≤ArA_l-d \le A_r。该部分答案即为 (r−l+1)(r-l+1)。答案求累乘。乘法原理证明。由于 ll 单调不降，则时间复杂度瓶颈在排序的 O(nlog⁡n)O(n \log n)。这样就搞定了双倍经验那题。
然后你的样例一错了……
你发现当 AiA_i 相同时看做 11 个答案。所以我们要除去每种值出现多的部分。考虑用 map\text{map} 记录 AiA_i 元素出现次数。则不难发现，对于值 xx，你需要除以掉 ∏i=1mpxi\displaystyle\prod_{i=1}^{mp_x} i。考虑费马小定理求逆元。
即原本答案为 ansans，则现在的答案就是 ans∏x∈A∏i=1mpxi\frac{ans}{\displaystyle\prod_{x\in A}\displaystyle\prod_{i=1}^{mp_x} i}。
总时间复杂度为 O(nlog⁡n)O(n \log n)。

代码

CPP
#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;
}
撒花！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...