70pts 卡常有希望过吗
查看原帖
70pts 卡常有希望过吗
555065
ChrysanthBlossom楼主2024/7/8 08:44

对 aa 离散化(最后只有 O(V)O(\sqrt{V}) 个值),然后暴力 O(n2)O(n^2) 算,复杂度 O(V)O(V)。

感觉可能可以卡过去,毕竟 4s 啊, 4s 啊,4s 啊!!!!!

#include<bits/stdc++.h>
#define ri register int
#define ll unsigned long long
using namespace std;
const int maxn=1e6+7;
const int mod=998244353;
int n;
int a[maxn];
int lsh[maxn];
int tot;
int tong[maxn];
namespace IO {
	int len = 0;
	char ibuf[(1 << 20) + 1], *iS, *iT, out[(1 << 25) + 1];
#define gh()                                                            \
	(iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1,stdin),	\
	(iS == iT ? EOF : *iS++) : *iS++)
	inline ll read() {
		char ch = gh();
		ll x = 0;
		char t = 0;
		while (ch < '0' || ch > '9')
			t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9')
			x = (x << 3) + (x << 1) + (ch ^ 48), ch = gh();
		return t ? -x : x;
	}
	inline void putc(char ch) {
		out[len++] = ch;
	}
	template <class T> inline void write(T x) {
		if (x < 0)
			putc('-'), x = -x;
		if (x > 9)
			write(x / 10);
		out[len++] = x % 10 + 48;
	}
	template < > inline void write<const char*> (const char* x) {
		int i=0;
		while(x[i]!='\0') out[len++] = x[i++];
	}
	template < > inline void write<char*> (char* x) {
		int i=0;
		while(x[i]!='\0') out[len++] = x[i++];
	}
	template <class T> inline void write(T x,char a){
		write(x);
		out[len++] = a;
	}
	inline void flush() {
		fwrite(out, 1, len, stdout);
		len = 0;
	}
}
using IO::flush;
using IO::putc;
using IO::read;
using IO::write;
ll llsh[maxn];
int ttot;
ll b[maxn];
int ttong[maxn];
signed main(){
	ios::sync_with_stdio(0);
	ll m;
	n=read();m=read();
	for(ri i=1;i<=n;i++){
		a[i]=read();
		lsh[i]=a[i];
	}
	sort(lsh+1,lsh+1+n);
	tot=unique(lsh+1,lsh+1+n)-lsh-1;
	for(ri i=1;i<=n;i++){
		a[i]=lower_bound(lsh+1,lsh+1+tot,a[i])-lsh;
	}
	for(ri i=1;i<=n;i++)tong[a[i]]++;
	for(ri i=1;i<=tot;i++){
		b[i]=m/lsh[i];
		llsh[++ttot]=b[i];
	}
	sort(llsh+1,llsh+1+ttot);
	ttot=unique(llsh+1,llsh+1+ttot)-llsh-1;
	for(ri i=1;i<=tot;i++){
		ttong[lower_bound(llsh+1,llsh+1+ttot,b[i])-llsh]+=tong[i];
	}
	int ans=0;
	for(ri i=1;i<=ttot;i++){
		for(ri j=1;j<=tot;j++){
			ans=ans+(llsh[i]/lsh[j])*ttong[i]%mod*tong[j]%mod;
			if(ans>mod)ans-=mod;
		}
	}
	write(ans);
	flush();
	return 0;
}
2024/7/8 08:44
加载中...