E. Expected Damage
强度 (ge b) 的怪物地位是相同的，(< b) 同理，可以直接取平均值。
(ge b) 的贡献很容易计算，(<b) 的考虑分开计算，设有 (c) 个强度 (ge b) 的，那么每个 (<b) 的怪物对答案有贡献的概率是 (frac{c + 1 - a}{c + 1})（只考虑 (ge b) 的和它本身）。
复杂度 (mathcal O((n + q)log n + q log mod))
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
template<class T>
inline void read(T &x) {
char ch; int f = 1;
x = 0;
while(isspace(ch = getc()));
if(ch == '-') ch = getc(), f = -1;
do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
x *= f;
}
template<class T, class ...Args>
inline void read(T &x, Args&... args) {read(x); read(args...);}
template<class T>
inline void write(T x) {
static char stk[128];
int top = 0;
if(x == 0) {putc('0'); return;}
if(x < 0) putc('-'), x = -x;
while(x) stk[top++] = x % 10, x /= 10;
while(top) putc(stk[--top] + '0');
}
template<class T, class ...Args>
inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
inline void space() {putc(' ');}
inline void endl() {putc('
');}
struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;
const int M = 998244353;
inline int add(int x, int y) {return x+y>=M ? x+y-M : x+y;}
template<class ...Args> inline int add(int x, int y, Args... args) {return add(add(x, y), args...);}
inline int sub(int x, int y) {return x-y<0 ? x-y+M : x-y;}
inline int mul(int x, int y) {return 1LL * x * y % M;}
template<class ...Args> inline int mul(int x, int y, Args... args) {return mul(mul(x, y), args...);}
inline void inc(int &x, int y=1) {x += y; if(x >= M) x -= M;}
inline void dec(int &x, int y=1) {x -= y; if(x < 0) x += M;}
inline int power(int x, int y){
int res = 1;
for(; y; y>>=1, x = mul(x, x)) if(y & 1) res = mul(res, x);
return res;
}
inline int inv(int x){return power(x, M - 2);}
const int N = 200005;
int d[N], s[N];
int main() {
// File("cf1418e");
int n, m;
read(n, m);
int facn = 0;
for (int i = 1; i <= n; ++i)
facn = 1LL * facn * i % M;
for (int i = 1; i <= n; ++i)
read(d[i]);
sort(d + 1, d + 1 + n);
for (int i = 1; i <= n; ++i) s[i] = (s[i - 1] + d[i]) % M;
for (int i = 1; i <= m; ++i) {
int a, b;
read(a, b);
int L = lower_bound(d + 1, d + 1 + n, b) - d - 1, H = n - L;
if (H < a) {
write(0), endl();
continue;
}
int sH = sub(s[n], s[n - H]), sL = s[L];
int avgH = mul(sH, inv(H));
int cH = mul(H - a, avgH);
int cL = mul(H + 1 - a, inv(H + 1), sL);
write(add(cH, cL)), endl();
}
return 0;
}
F. Equal Product
由 (x_1y_1 = x_2y_2)
[frac{x_1}{y_2} = frac{x_2}{y_1} = frac{a}{b} qquad gcd(a, b) = 1
]
枚举 (x_1)，算出 (y_1) 的范围 ([frac{L}{x_1}, min{frac{R}{x_1},m}])，枚举 (a mid x_1)。
设 (x_2 = ka)，由 (k) 可以算出 (b) 的范围，这可以整除分块，注意到上限是 (m)。
逐一检查即可，代码写的很清楚。复杂度上界 (mathcal O(n^{1.5} log n))。
跑的很快，可能可以分析出更优的上界。
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
namespace io {
#define File(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1;
inline char getc () {return (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++);}
inline void flush () {fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
inline void putc (char x) {*oS ++ = x; if (oS == oT) flush ();}
template<class T>
inline void read(T &x) {
char ch; int f = 1;
x = 0;
while(isspace(ch = getc()));
if(ch == '-') ch = getc(), f = -1;
do x = x * 10 + ch - '0'; while(isdigit(ch = getc()));
x *= f;
}
template<class T, class ...Args>
inline void read(T &x, Args&... args) {read(x); read(args...);}
template<class T>
inline void write(T x) {
static char stk[128];
int top = 0;
if(x == 0) {putc('0'); return;}
if(x < 0) putc('-'), x = -x;
while(x) stk[top++] = x % 10, x /= 10;
while(top) putc(stk[--top] + '0');
}
template<class T, class ...Args>
inline void write(T x, Args... args) {write(x); putc(' '); write(args...);}
inline void space() {putc(' ');}
inline void endl() {putc('
');}
struct _flush {~_flush() {flush();}} __flush;
};
using io::read; using io::write; using io::flush; using io::space; using io::endl; using io::getc; using io::putc;
const int N = 200004;
vector<int> divisor[N];
int main() {
// File("cf1418f");
int n, m;
ll L, R;
read(n, m, L, R);
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; j += i)
divisor[j].push_back(i);
for (int x1 = 1; x1 < n; ++x1) { // x1 / y2 = x2 / y1 = a / b, where gcd(a, b) = 1
ll left = max((L - 1) / x1 + 1, 1LL), right = min(R / x1, ll(m)); // bound for y1
// x1 * y1 in [L, R], left, right in [1, m]
if (left > right) {
write(-1), endl();
continue;
}
bool flag = false;
for (int d : divisor[x1]) {
int a = x1 / d;
for (int k = x1 / a + 1, li = n / a, nxt; k <= li; k = nxt + 1) { // x2 = k * a
nxt = 0x3fffffff;
if (left > k) nxt = min(ll(nxt), (left - 1) / ((left - 1) / k));
if (right >= k) nxt = min(ll(nxt), right / (right / k));
int lb = (left - 1) / k + 1, rb = right / k; // bound for b, since y1 = kb
if (lb <= rb && lb * d <= m) {
write(x1, k * lb, k * a, d * lb), endl();
flag = true;
break;
}
}
if (flag) break;
}
if(!flag) write(-1), endl();
}
write(-1), endl();
return 0;
}