A – AtCoder Line (abc352 A)
题目大意
给定(x, y,z),问 (z)是否在(x,y)之间。
解题思路
如果(x > y),则交换 (x,y),然后判断是否有 (x leq z leq y)即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, x, y, z;
cin >> n >> x >> y >> z;
if (x > y)
swap(x, y);
if (x
B – Typing (abc352 B)
题目大意
给定字符串(s,t)。 (s)是 (t)的子序列。现就近匹配,找到 (s)的每个字符就近匹配到的 (t)中的每个下标。
解题思路
按照就近匹配原则,匹配一次子序列即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s, t;
cin >> s >> t;
auto pos = t.begin();
for (auto c : s) {
while (pos != t.end() && *pos != c) {
pos = next(pos);
}
cout
C – Standing On The Shoulders (abc352 C)
题目大意
给定(n)个巨人,巨人有肩高(a_i)和头高(b_i)。
现依次放置每个巨人,每个巨人放在上一个巨人的肩上。
问最高的巨人的头高有多高。
解题思路
枚举最后的巨人是哪个,那么其头高就是(b_i + sum_{j neq i} a_j)。
所有可能的情况取最大值即为答案。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n), b(n);
for (int i = 0; i > a[i] >> b[i];
LL suma = accumulate(a.begin(), a.end(), 0LL);
LL ans = 0;
for (int i = 0; i
D – Permutation Subsequence (abc352 D)
题目大意
给定一个排列(p_i)和一个数(k)。
找出(k)个下标,最小化下标极差,使得对应的(p_i)组成的集合是一个连续的 (k)个数的集合。
解题思路
记 (pos[i])表示数 (i)在原排列的位置。枚举这连续的(k)个数,比如是(i,i+1,i+2,…,i+k-1),那此时的极差就是 (max_{i leq j leq i+k-1}(pos[j]) – min_{i leq j leq i+k-1}(pos[j]))
对所有的(i)取最小值,就是答案。
按顺序枚举(i),此时就是求一个长度为 (k)的 (pos)区间的最大值和最小值,即经典的滑动窗口问题,用单调维护即可。
神奇的代码
#include
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
vector pos(n);
for (int i = 0; i > x;
--x;
pos[x] = i;
}
int ans = n + 1;
deque minn, maxx;
for (int i = 0; i = k) {
minn.pop_front();
}
while (!maxx.empty() && i - maxx.front() >= k) {
maxx.pop_front();
}
while (!minn.empty() && pos[i] = pos[maxx.back()]) {
maxx.pop_back();
}
minn.push_back(i);
maxx.push_back(i);
if (i >= k - 1)
ans = min(ans, pos[maxx.front()] - pos[minn.front()]);
}
cout
E – Clique Connect (abc352 E)
题目大意
给定一张无向图,初始无边。
现依次进行(q)次操作,每次操作给定 (k_i)个点 (x_{i,j})和边权 (c_i),将这 (k_i)个点俩俩 连边,边权为(c)。
问最后图是否连通,若连通,问最小生成树的权值。
解题思路
用并查集维护连通性,对于每次操作,就依次合并相邻两点(x_{i,j},x_{i,j+1})即可。那么总的复杂度是(O(sum k_i))。考虑如何求最小生成树。
参考(kruskal)算法,直接从边权最小的开始连边,连边就(x_{i,j},x_{i,j+1})相连即可,如果它们未相连的话。这个过程可以在并查集合并时顺便做了。
因此时间复杂度就是(O(sum k_i))。
神奇的代码
#include
using namespace std;
using LL = long long;
class dsu {
public:
vector p;
vector sz;
int n;
dsu(int _n) : n(_n) {
p.resize(n);
sz.resize(n);
iota(p.begin(), p.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
sz[y] += sz[x];
return true;
}
return false;
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector, int>> a(m);
for (auto& [p, c] : a) {
int k;
cin >> k >> c;
p.resize(k);
for (auto& i : p) {
cin >> i;
--i;
}
}
vector id(m);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(),
[&](int i, int j) { return a[i].second
F – Estimate Order (abc352 F)
题目大意
(n)个人,排名唯一,给定关于这些人的(m)条排名信息,问每个人的名次是否能唯一确定。
信息为(i,j,c_k),表示第(i)个人的名次 (r_i)与第 (j)个人的名字 (r_j) 的差(r_i – r_j = c_k)。
解题思路
神奇的代码
G – Socks 3 (abc352 G)
题目大意
抽屉里有(n)个颜色的袜子,各有 (a_i)只。
现每次从抽屉里等概率取一只袜子,不放回,直到取出两只颜色相同的袜子为止。
问取出的袜子的期望只数。
解题思路
假设恰好取出(i)只袜子后,有两只颜色相同的概率是 (q_i),那么期望次数即为 (sum i q_i)。(这个式子比较经典,是一个前缀和的前缀和的展开式。)
假设取出(i)只或以上后,有两只颜色相同的概率是 (p_i),即 (p_i = sum_{j geq i} q_i),是个后缀和,则 (q_i = p_{i} – p_{i+1})。代替上述期望式子得 (sum p_i)。
(p_{i+1})表示需要取超过(i)只袜子才能有两只袜子颜色相同的概率,换句话说,它就是取(i)只袜子,没有两只颜色相同的概率(这才需要取(i+1)只或以上才能有两只袜子颜色相同,它不意味着第 (i+1)只能取到颜色相同)。
而取(i)只颜色各不相同的概率,可先枚举对应的 (i)种颜色,然后(frac{text{对应数量相乘}}{text{总情况数}})。从生成函数的角度考虑,每种颜色的生成函数是 (a_i x + 1),则所有颜色的生成函数相乘 ((a_1x+1)(a_2x+1)…(a_nx+1))的结果的 (x_i)的系数就是上述的分子,分母(总情况数)就是 (C_{tot}^k) ,(tot = sum a_i)。
因此需要求出 ((a_1x+1)(a_2x+1)…(a_nx+1))的结果,朴素的乘法需要进行(O(n))次,每次用 (ntt)优化的话,总复杂度也得是 (O(n^2 log n))。
因为每次相乘,多项式的最高幂才 (+1),可以考虑分治,假设(f(l,r) = prod_{l leq i leq r} (a_ix + 1)),要求(f(1,n)),则先求 (f(1, frac{n}{2}))和 (f(frac{n}{2} + 1, n)),再两者相乘,就得到 (f(1,n)),而 (f(1, frac{n}{2}))和 (f(frac{n}{2} + 1, n))就递归求解。这样每次相乘,多项式的最高幂就会翻倍,最多翻(log)次就得到结果,而不是之前的(n)次。即总的时间复杂度是 (O(n log^2 n))。
代码是贴了(tourist)的 (ntt)板子和取模板子。
神奇的代码
#include
using namespace std;
using LL = long long;
template T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a;
swap(a, m);
u -= t * v;
swap(u, v);
}
assert(m == 1);
return u;
}
template class Modular {
public:
using Type = typename decay::type;
constexpr Modular() : value() {}
template Modular(const U& x) { value = normalize(x); }
template static Type normalize(const U& x) {
Type v;
if (-mod() (x);
else
v = static_cast(x % mod());
if (v explicit operator U() const {
return static_cast(value);
}
constexpr static Type mod() { return T::value; }
Modular& operator+=(const Modular& other) {
if ((value += other.value) >= mod())
value -= mod();
return *this;
}
Modular& operator-=(const Modular& other) {
if ((value -= other.value) Modular& operator+=(const U& other) {
return *this += Modular(other);
}
template Modular& operator-=(const U& other) {
return *this -= Modular(other);
}
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) {
Modular result(*this);
*this += 1;
return result;
}
Modular operator--(int) {
Modular result(*this);
*this -= 1;
return result;
}
Modular operator-() const { return Modular(-value); }
template
typename enable_if::Type, int>::value,
Modular>::type&
operator*=(const Modular& rhs) {
#ifdef _WIN32
uint64_t x =
static_cast(value) * static_cast(rhs.value);
uint32_t xh = static_cast(x >> 32),
xl = static_cast(x), d, m;
asm("divl %4; nt" : "=a"(d), "=d"(m) : "d"(xh), "a"(xl), "r"(mod()));
value = m;
#else
value = normalize(static_cast(value) *
static_cast(rhs.value));
#endif
return *this;
}
template
typename enable_if::Type, int64_t>::value,
Modular>::type&
operator*=(const Modular& rhs) {
int64_t q = static_cast(static_cast(value) *
rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template
typename enable_if::Type>::value,
Modular>::type&
operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}
Modular& operator/=(const Modular& other) {
return *this *= Modular(inverse(other.value, mod()));
}
template
friend bool operator==(const Modular& lhs, const Modular& rhs);
template
friend bool operator& lhs, const Modular& rhs);
template
friend std::istream& operator>>(std::istream& stream, Modular& number);
private:
Type value;
};
template
bool operator==(const Modular& lhs, const Modular& rhs) {
return lhs.value == rhs.value;
}
template
bool operator==(const Modular& lhs, U rhs) {
return lhs == Modular(rhs);
}
template
bool operator==(U lhs, const Modular& rhs) {
return Modular(lhs) == rhs;
}
template
bool operator!=(const Modular& lhs, const Modular& rhs) {
return !(lhs == rhs);
}
template
bool operator!=(const Modular& lhs, U rhs) {
return !(lhs == rhs);
}
template
bool operator!=(U lhs, const Modular& rhs) {
return !(lhs == rhs);
}
template
bool operator& lhs, const Modular& rhs) {
return lhs.value
Modular operator+(const Modular& lhs, const Modular& rhs) {
return Modular(lhs) += rhs;
}
template
Modular operator+(const Modular& lhs, U rhs) {
return Modular(lhs) += rhs;
}
template
Modular operator+(U lhs, const Modular& rhs) {
return Modular(lhs) += rhs;
}
template
Modular operator-(const Modular& lhs, const Modular& rhs) {
return Modular(lhs) -= rhs;
}
template
Modular operator-(const Modular& lhs, U rhs) {
return Modular(lhs) -= rhs;
}
template
Modular operator-(U lhs, const Modular& rhs) {
return Modular(lhs) -= rhs;
}
template
Modular operator*(const Modular& lhs, const Modular& rhs) {
return Modular(lhs) *= rhs;
}
template
Modular operator*(const Modular& lhs, U rhs) {
return Modular(lhs) *= rhs;
}
template
Modular operator*(U lhs, const Modular& rhs) {
return Modular(lhs) *= rhs;
}
template
Modular operator/(const Modular& lhs, const Modular& rhs) {
return Modular(lhs) /= rhs;
}
template
Modular operator/(const Modular& lhs, U rhs) {
return Modular(lhs) /= rhs;
}
template
Modular operator/(U lhs, const Modular& rhs) {
return Modular(lhs) /= rhs;
}
template
Modular power(const Modular& a, const U& b) {
assert(b >= 0);
Modular x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1)
res *= x;
x *= x;
p >>= 1;
}
return res;
}
template string to_string(const Modular& number) {
return to_string(number());
}
template
std::ostream& operator& number) {
return stream
std::istream& operator>>(std::istream& stream, Modular& number) {
typename common_type::Type, int64_t>::type x;
stream >> x;
number.value = Modular::normalize(x);
return stream;
}
constexpr int md = 998244353;
using Mint = Modular::type, md>>;
template class NTT {
public:
using Type = typename decay::type;
static Type md;
static Modular root;
static int base;
static int max_base;
static vector> roots;
static vector rev;
static void clear() {
root = 0;
base = 0;
max_base = 0;
roots.clear();
rev.clear();
}
static void init() {
md = T::value;
assert(md >= 3 && md % 2 == 1);
auto tmp = md - 1;
max_base = 0;
while (tmp % 2 == 0) {
tmp /= 2;
max_base++;
}
root = 2;
while (power(root, (md - 1) >> 1) == 1) {
root++;
}
assert(power(root, md - 1) == 1);
root = power(root, (md - 1) >> max_base);
base = 1;
rev = {0, 1};
roots = {0, 1};
}
static void ensure_base(int nbase) {
if (md != T::value) {
clear();
}
if (roots.empty()) {
init();
}
if (nbase > 1] >> 1) + ((i & 1) z = power(root, 1 >& a) {
int n = (int)a.size();
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for (int i = 0; i > shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for (int k = 1; k x = a[i + j];
Modular y = a[i + j + k] * roots[j + k];
a[i + j] = x + y;
a[i + j + k] = x - y;
}
}
}
}
static vector> multiply(vector> a,
vector> b) {
if (a.empty() || b.empty()) {
return {};
}
int eq = (a == b);
int need = (int)a.size() + (int)b.size() - 1;
int nbase = 0;
while ((1 inv_sz = 1 / static_cast>(sz);
for (int i = 0; i typename NTT::Type NTT::md;
template Modular NTT::root;
template int NTT::base;
template int NTT::max_base;
template vector> NTT::roots;
template vector NTT::rev;
template vector> inverse(const vector>& a) {
assert(!a.empty());
int n = (int)a.size();
vector> b = {1 / a[0]};
while ((int)b.size() > x(a.begin(),
a.begin() + min(a.size(), b.size() > c = b;
NTT::fft(c);
NTT::fft(x);
Modular inv = 1 / static_cast>((int)x.size());
for (int i = 0; i ::fft(x);
rotate(x.begin(), x.begin() + (x.size() >> 1), x.end());
fill(x.begin() + (x.size() >> 1), x.end(), 0);
NTT::fft(x);
for (int i = 0; i ::fft(x);
for (int i = 0; i > 1); i++) {
b[i + ((int)x.size() >> 1)] = -x[i];
}
}
b.resize(n);
return b;
}
template vector> inverse_old(vector> a) {
assert(!a.empty());
int n = (int)a.size();
if (n == 1) {
return {1 / a[0]};
}
int m = (n + 1) >> 1;
vector> b =
inverse(vector>(a.begin(), a.begin() + m));
int need = n ::ensure_base(nbase);
int size = 1 ::fft(a);
NTT::fft(b);
Modular inv = 1 / static_cast>(size);
for (int i = 0; i ::fft(a);
a.resize(n);
return a;
}
template
vector> operator*(const vector>& a,
const vector>& b) {
if (a.empty() || b.empty()) {
return {};
}
if (min(a.size(), b.size()) > c(a.size() + b.size() - 1, 0);
for (int i = 0; i ::multiply(a, b);
}
template
vector>& operator*=(vector>& a,
const vector>& b) {
return a = a * b;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector a(n);
for (auto& x : a)
cin >> x;
int tot = accumulate(a.begin(), a.end(), 0);
auto solve = [&](auto solve, int l, int r) -> vector {
if (l + 1 == r)
return {1, a[l]};
int m = (l + r) >> 1;
return solve(solve, l, m) * solve(solve, m, r);
};
vector poly = solve(solve, 0, n);
Mint deno = 1, ans = 0;
for (int i = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net