[LibreOJ 2182][SDOI2015]寻宝游戏
很多人说事动态虚树……其实也不算是吧，虽然这个东西用力虚树的思路惹。
第一个想到的思路……就事动态的维护虚树，然后虚树上所有边的长度乘二就事答案。然后我们考虑一点……虚树求的时候需要对DFS序（严格来说事欧拉序）排序，所以我们大致可以认为，虚树上做欧拉回路的本质就事按照DFS序扫描，换言之就事DFS一遍，然后进入和回溯事都把边记录到答案里，这个值也就事虚树上按DFS序排序之后两两相邻点的距离的和（首尾也要额外算一遍）。
然后这样一来，我们发现虚树上的非关键点就可以删掉了。因为非关键点也就是所有两两在DFS序中相邻的关键点的LCA，然后那两个关键点的距离也就等于他们到这个非关键点的距离的和。因此我们不需要维护非关键点，问题就简单了许多……
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
const int maxn = 100005;
using ll = long long;
using pii = std::pair<int, ll>;
std::vector<pii> G[maxn];
void add_edge(int u, int v, ll w) {
G[u].push_back(pii(v, w));
}
void ins_edge(int u, int v, ll w) {
add_edge(u, v, w); add_edge(v, u, w);
}
int anc[maxn][17];
int dep[maxn], dfn[maxn]; ll dis[maxn];
int dcnt = 0;
void dfs(int x, int fa = -1) {
anc[x][0] = fa; dfn[x] = ++ dcnt;
for(auto &e : G[x]) {
int v = e.first; ll w = e.second;
if(v != fa) {
dep[v] = dep[x] + 1;
dis[v] = dis[x] + w;
dfs(v, x);
}
}
}
int n;
void process() {
memset(anc, -1, sizeof(anc)); dfs(1);
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = anc[i][j - 1];
if(a != -1) {
anc[i][j] = anc[a][j - 1];
}
}
}
}
int lca(int u, int v) {
if(dep[u] < dep[v]) std::swap(u, v);
for(int j = 16; j >= 0; j --) {
int a = anc[u][j];
if(a != -1 && dep[a] >= dep[v]) {
u = a;
}
}
if(u == v) return u;
for(int j = 16; j >= 0; j --) {
int a1 = anc[u][j], a2 = anc[v][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
u = a1; v = a2;
}
}
return anc[u][0];
}
ll calc_dist(int u, int v) {
return dis[u] + dis[v] - 2LL * dis[lca(u, v)];
}
// template <typename T>
struct Comp {
bool operator ()(const int &a, const int &b) const {
return dfn[a] < dfn[b];
}
};
ll now = 0LL; std::set<int, Comp> S;
bool sta[maxn];
void add(int p) {
auto suc = S.upper_bound(p);
if(suc != S.begin()) {
auto pre = -- suc; ++ suc;
now += calc_dist(*pre, p);
if(suc != S.end()) {
now -= calc_dist(*pre, *suc);
}
}
if(suc != S.end()) {
now += calc_dist(*suc, p);
}
S.insert(p);
}
void del(int p) {
auto suc = S.upper_bound(p);
if(suc != S.end()) {
now -= calc_dist(*suc, p);
}
if((*S.begin()) != p) {
-- suc; -- suc;
int prev = *suc;
now -= calc_dist(prev, p);
++ suc; ++ suc;
if(suc != S.end()) {
now += calc_dist(prev, *suc);
}
}
S.erase(p);
}
ll query() {
if(S.size() <= 1) return 0LL;
ll ret = now;
auto las = S.end(); -- las;
ret += calc_dist(*S.begin(), *las);
return ret;
}
int main() {
int m; scanf("%d%d", &n, &m);
for(int i = 1; i <= n - 1; i ++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
ins_edge(u, v, w);
}
process();
while(m --) {
int x; scanf("%d", &x);
if(sta[x]) {
del(x);
} else {
add(x);
}
sta[x] = !sta[x];
printf("%lld\n", query());
}
return 0;
}
[LibreOJ 6436][PKUSC2018]神仙的游戏
考场上写炸了FFT的zzs事野蛮人（确信）
兄啊这题怎么还卡常啊！
不妨设\(n = |S|\)。那么如果串有一个长度为$i$的border，就意味着串有一个长度为\(n - i\)的循环节。
那么考虑有两个非?的位置\(i\)和\(j\)（不妨设\(i < j\)），且\(S_i\neq S_j\)。那么我们设\(l = j - i\)，则\(l\)的约数都不能成为循环节的长度，否则会出现矛盾（一个位置又要是0又要是1）。
那么考虑对于所有可能的\(l\)判定是否存在这种不合法的\(i\)与\(j\)。我们利用编辑距离函数：
\[f_l = \sum_{i} A_i A_{i + l}(A_i - A_{i + l})^2\]
这里\(A_i\)相当于\(S_i\)的一个重编码，\(S_i\)为?时应当为0，其他情况一种为1一种为2。这个函数不方便我们卷积，所以我们考虑把\(A\)翻转一下（新的序列称为\(B\)）：
\[
\begin{aligned}
f_l &= \sum_{i} B_{n - i - 1} A_{i + l}(B_{n - i - 1} A_{i + l})^2\\
&= \sum_{i} B_{n - i - 1}^3 A_{i + l} - 2B_{n - i - 1}^2 A_{i + l}^2 + B_{n - i - 1}A_{i + l}^3
\end{aligned}\]
然后问题变成了三个卷积。FFT一下就行了（请注意IDFT只需要一次……否则会被卡常）。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cmath>
#include <complex>
#include <vector>
using R = double;
struct C {
R x, y;
C(R xx = 0.00, R yy = 0.00) {
x = xx; y = yy;
}
R real() {
return x;
}
};
C operator +(const C &a, const C &b) {
return C(a.x + b.x, a.y + b.y);
}
C operator -(const C &a, const C &b) {
return C(a.x - b.x, a.y - b.y);
}
C operator *(const C &a, const C &b) {
return C(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
using ll = long long;
constexpr R pi = acos(-1);
int flip(int bi, int x) {
int ret = 0;
for(int i = 0; i < bi; i ++) {
if(x & (1 << i)) {
ret += (1 << (bi - i - 1));
}
}
return ret;
}
void FFT(C *A, int bi, R flag = 1.00) {
int n = 1 << bi;
for(int i = 0; i < n; i ++) {
int v = flip(bi, i);
if(i < v) std::swap(A[v], A[i]);
}
for(int L = 1; L < n; L <<= 1) {
R rd = pi / (R(L));
C xi_n(cos(rd), sin(flag * rd));
for(int j = 0; j < n; j += (L << 1)) {
C xi(1.00, 0.00);
for(int i = j; i < j + L; i ++) {
C x = A[i], y = A[i + L];
A[i] = x + xi * y;
A[i + L] = x - xi * y;
xi = xi * xi_n;
}
}
}
}
const int maxn = 500005;
R tot[maxn];
C T[maxn << 2], TT[maxn << 2], D[maxn << 2];
char S[maxn];
inline int conv(char c) {
if(c == '1') return 2;
if(c == '0') return 1;
return 0;
}
int A[maxn], B[maxn];
bool boom[maxn];
int main() {
scanf("%s", S); int n = strlen(S);
for(int i = 0; i < n; i ++) {
A[i] = B[n - 1 - i] = conv(S[i]);
}
int len = 1, bi = 0;
while(len < (2 * n)) {
len <<= 1; bi ++;
}
C z(0.00, 0.00);
// std::fill(T, T + len, z);
// std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i] * A[i] * A[i]; TT[i] = B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + (T[i] * TT[i]);
}
std::fill(T, T + len, z);
std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i] * A[i]; TT[i] = B[i] * B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + C(-2.00, 0.00) * (T[i] * TT[i]);
}
std::fill(T, T + len, z);
std::fill(TT, TT + len, z);
for(int i = 0; i < n; i ++) {
T[i] = A[i]; TT[i] = B[i] * B[i] * B[i];
}
FFT(T, bi); FFT(TT, bi);
for(int i = 0; i < len; i ++) {
D[i] = D[i] + (T[i] * TT[i]);
}
FFT(D, bi, -1.00);
for(int i = 1; i < n; i ++) {
if(fabs(D[n - 1 + i].real() / (R(len))) > 0.99) {
boom[i] = true;
}
}
for(int i = 1; i <= n; i ++) {
for(int j = i * 2; j <= n; j += i) {
boom[i] = (boom[i] || boom[j]);
}
}
ll ret = 0LL;
for(int i = 1; i <= n; i ++) {
if(!boom[n - i]) {
ret ^= (ll(i)) * (ll(i));
}
}
printf("%lld\n", ret);
return 0;
}
[LibreOJ 2562][SDOI2018]战略游戏
aji圆方树毁我青春，，，省选现场看出来是圆方树但写不出点双滚粗。
显然可以割的点是某两个点的某一条简单路径上的割点，然后两点间的简单路劲的并就是圆方树上的路径，割点在圆方树上就是非叶子的圆点。我们求所有两点路径的并，就需要虚树。
然后做完了……直接建圆方树，每次询问建虚树xjb统计即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
const int maxn = 100005;
const int maxm = 200005;
std::vector<int> G[maxn];
void cz1() {
for(int i = 0; i < maxn; i ++) {
G[i].clear();
}
}
void add_edge1(int u, int v) {
G[u].push_back(v); G[v].push_back(u);
}
using pii = std::pair<int, int>;
int dcnt, bcc_cnt; int pre[maxn]; bool iscut[maxn];
int bccno[maxn]; std::vector<int> bcc[maxm];
int dfs(int x, int fa = -1) {
static std::stack<pii> S;
pre[x] = ++ dcnt; int low = pre[x];
int cld = 0;
for(auto v : G[x]) {
pii e = std::make_pair(x, v);
if(!pre[v]) {
S.push(e); cld ++;
int lowv = dfs(v, x);
low = std::min(low, lowv);
if(lowv >= pre[x]) {
iscut[x] = true; bcc_cnt ++;
bcc[bcc_cnt].clear();
while(true) {
pii ee = S.top(); S.pop();
int f = ee.first, g = ee.second;
if(bccno[f] != bcc_cnt) {
bccno[f] = bcc_cnt;
bcc[bcc_cnt].push_back(f);
}
if(bccno[g] != bcc_cnt) {
bccno[g] = bcc_cnt;
bcc[bcc_cnt].push_back(g);
}
if(f == x && g == v) break;
}
}
} else if(pre[v] < pre[x] && v != fa) {
S.push(e);
low = std::min(low, pre[v]);
}
}
return low;
}
int n, m;
void calc_bcc() {
std::fill(pre, pre + 1 + n, 0);
std::fill(iscut, iscut + 1 + n, false);
std::fill(bccno, bccno + 1 + m, 0);
dcnt = bcc_cnt = 0;
for(int i = 1; i <= n; i ++) {
if(!pre[i]) dfs(i);
}
}
std::vector<int> G2[maxn + maxm];
void cz2() {
for(int i = 0; i < maxn + maxm; i ++) G2[i].clear();
}
void add_edge2(int u, int v) {
G2[u].push_back(v); G2[v].push_back(u);
}
int anc[maxn + maxm][19], dep[maxn + maxm], d[maxn + maxm];
int dfn[maxn + maxm], siz[maxn + maxm];
int cnt2;
void dfs_tree(int x, int fa = -1, int depth = 0, int s = 0) {
#ifdef LOCAL
printf("V (%d, %d, %d, %d)\n", x, fa, depth, s);
#endif
cnt2 ++; dfn[x] = cnt2; siz[x] = 1;
d[x] = s; anc[x][0] = fa; dep[x] = depth;
for(auto v : G2[x]) {
if(v != fa) {
dfs_tree(v, x, depth + 1, s + ((v <= n) ? 1 : 0));
siz[x] += siz[v];
}
}
}
void process_lca() {
memset(anc, -1, sizeof(anc));
cnt2 = 0;
int s = bcc_cnt + n; dfs_tree(n + 1);
#ifdef LOCAL
printf("s : %d\n", s);
#endif
for(int j = 1; (1 << j) < s; j ++) {
for(int i = 1; i <= s; i ++) {
int a = anc[i][j - 1];
if(a != -1) anc[i][j] = anc[a][j - 1];
}
}
}
int lca(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
for(int j = 18; j >= 0; j --) {
int a = anc[x][j];
if(a != -1 && dep[a] >= dep[y]) {
x = a;
}
}
if(x == y) return x;
for(int j = 18; j >= 0; j --) {
int a1 = anc[x][j], a2 = anc[y][j];
if(a1 != -1 && a2 != -1 && a1 != a2) {
x = a1; y = a2;
}
}
return anc[x][0];
}
void process() {
calc_bcc();
cz2();
for(int i = 1; i <= bcc_cnt; i ++) {
int id = n + i;
for(auto u : bcc[i]) {
add_edge2(u, id);
}
}
process_lca();
}
int get_delta(int x, int y) { // y is x's ancestor.
return (d[anc[x][0]] - d[y]);
}
bool is_anc(int fa, int bef) {
int l1 = dfn[fa], r1 = dfn[fa] + siz[fa] - 1;
int l2 = dfn[bef], r2 = dfn[bef] + siz[bef] - 1;
return (l1 <= l2 && r2 <= r1);
}
int query(int sz) {
std::vector<int> V;
for(int i = 1; i <= sz; i ++) {
int x; scanf("%d", &x);
V.push_back(x);
}
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::set<int> ds; ds.insert(V[0]);
for(int i = 1; i < sz; i ++) {
ds.insert(V[i]);
ds.insert(lca(V[i - 1], V[i]));
}
V.clear(); for(auto u : ds) V.push_back(u);
std::sort(V.begin(), V.end(), [&](const int &i, const int &j) {
return dfn[i] < dfn[j];
});
std::stack<int> S;
int ans = 0;
for(int i = 0; i < V.size(); i ++) {
int u = V[i];
while(!S.empty() && !is_anc(S.top(), u)) {
S.pop();
}
if(!S.empty()) {
#ifdef LOCAL
printf("ans (%d, %d) : %d\n", u, S.top(), get_delta(u, S.top()));
#endif
ans += get_delta(u, S.top());
}
S.push(u);
}
for(auto u : ds) {
if(u <= n) ans ++;
}
ans -= sz;
return ans;
}
int main() {
int T; scanf("%d", &T);
while(T --) {
scanf("%d%d", &n, &m); cz1();
for(int i = 1; i <= m; i ++) {
int u, v; scanf("%d%d", &u, &v);
add_edge1(u, v);
}
process();
int q; scanf("%d", &q);
while(q --) {
int sz; scanf("%d", &sz);
printf("%d\n", query(sz));
#ifdef LOCAL
fflush(stdout);
#endif
}
}
return 0;
}
[LibreOJ 121]可离线动态图连通性
LCT+扫描线应该随便做吧这题……但我学了一下线段树分治
这个问题有删除非常的恶心，让我们考虑怎么去掉删除的影响。
每条边存在的时间段是一个区间，而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标，对所有询问建线段树，然后对一段区间加边就是一个区间打标记，最后扫一遍线段树就可以解决问题。
同时需要注意，这个题在DFS线段树的过程中，往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩，但是可以按轶合并。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
Node *fa; int siz;
Node() {
fa = NULL; siz = 1;
}
void sc(Node *c) {
siz += c -> siz;
c -> fa = this;
}
void brk() {
fa -> siz -= siz;
fa = NULL;
}
};
Node *r[maxn];
int n;
void init_set() {
for(int i = 1; i <= n; i ++) {
r[i] = new Node();
}
}
Node *get_fa(Node *x) {
if(x -> fa == NULL) {
return x;
} else {
return get_fa(x -> fa);
}
}
Node *link_set(Node *x, Node *y) {
if(x -> siz < y -> siz) std::swap(x, y);
x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
return (get_fa(x) == get_fa(y));
}
const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
if(ql <= L && R <= qr) {
event[o].push_back(e);
} else {
int M = (L + R) / 2;
if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
}
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
if(L == R) {
que[o] = e;
} else {
int M = (L + R) / 2;
if(p <= M) {
add_query(o << 1, L, M, p, e);
} else {
add_query(o << 1 | 1, M + 1, R, p, e);
}
}
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
for(auto e : event[o]) {
int u = e.first, v = e.second;
if(!is_same(r[u], r[v])) {
#ifdef LOCAL
printf("Merging %d and %d.\n", u, v);
#endif
S.push(std::make_pair(merge_set(r[u], r[v]), o));
}
}
if(L == R) {
int u = que[o].first, v = que[o].second;
if(u == -1 && v == -1) {
ret[L] = -1;
} else {
if(is_same(r[u], r[v])) {
ret[L] = 1;
} else {
ret[L] = 0;
}
}
} else {
int M = (L + R) / 2;
solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
}
while(!S.empty() && S.top().second >= o) {
Node *u = S.top().first; S.pop();
u -> brk();
}
}
std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
int m; scanf("%d%d", &n, &m);
init_set();
pii fl(-1, -1);
for(int i = 1; i <= m; i ++) {
pii e; int op;
scanf("%d%d%d", &op, &e.first, &e.second);
if(e.first > e.second) {
std::swap(e.first, e.second);
}
if(op == 2) {
add_query(1, 1, m, i, e);
} else {
add_query(1, 1, m, i, fl);
V.push_back(e);
if(op == 0) {
ma[e].push(i);
} else {
int last = ma[e].top(); ma[e].pop();
add_event(1, 1, m, last, i - 1, e);
}
}
}
for(auto e : V) {
while(!ma[e].empty()) {
int g = ma[e].top(); ma[e].pop();
add_event(1, 1, m, g, m, e);
}
}
solve(1, 1, m);
for(int i = 1; i <= m; i ++) {
if(ret[i] != -1) {
if(ret[i]) {
puts("Y");
} else {
puts("N");
}
}
}
return 0;
}
[LibreOJ 2558][LNOI2014]LCA
现在才做这题TAT
如果询问的是一个子集和\(z\)的所有LCA的深度的和，那可以把子集里每一个元素到根的路径全部加1，然后根到\(z\)的路径上的和就是答案。
如果是区间的话，每次都扫一次整个区间一定会T……所以考虑把区间拆成两个前缀区间，然后离线，给询问排个序然后就好做了。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
using ll = long long;
const ll ha = 201314LL;
std::vector<int> G[maxn];
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
const int maxno = maxn << 2;
ll sumv[maxno], addv[maxno];
void maintain(int o) {
sumv[o] = (sumv[o << 1] + sumv[o << 1 | 1]) % ha;
}
void paint(int o, int L, int R, ll v) {
v %= ha;
addv[o] += v; addv[o] %= ha;
sumv[o] += (v * (ll(R - L + 1))) % ha; sumv[o] %= ha;
}
void pushdown(int o, int L, int R) {
if(addv[o] != 0LL) {
ll v = addv[o]; addv[o] = 0;
int M = (L + R) / 2;
int lc = o << 1, rc = o << 1 | 1;
paint(lc, L, M, v); paint(rc, M + 1, R, v);
}
}
int ql, qr; ll v;
void modify(int o, int L, int R) {
if(ql <= L && R <= qr) {
paint(o, L, R, v);
} else {
pushdown(o, L, R);
int M = (L + R) / 2;
if(ql <= M) modify(o << 1, L, M);
if(qr > M) modify(o << 1 | 1, M + 1, R);
maintain(o);
}
}
ll query(int o, int L, int R) {
if(ql <= L && R <= qr) {
return sumv[o];
} else {
pushdown(o, L, R);
int M = (L + R) / 2;
ll ans = 0;
if(ql <= M) ans = (ans + query(o << 1, L, M)) % ha;
if(qr > M) ans = (ans + query(o << 1 | 1, M + 1, R)) % ha;
return ans;
}
}
int siz[maxn], fa[maxn], dep[maxn], hson[maxn];
void dfs_1(int x, int f = 0, int depth = 0) {
fa[x] = f; dep[x] = depth; siz[x] = 1;
int maxs = 0;
for(auto v : G[x]) {
if(v != f) {
dfs_1(v, x, depth + 1);
siz[x] += siz[v];
if(siz[v] > maxs) {
maxs = siz[v]; hson[x] = v;
}
}
}
}
int top[maxn], tid[maxn], dfn[maxn];
void dfs_2(int x, int a) {
static int cnt = 0; cnt ++;
top[x] = a; tid[cnt] = x; dfn[x] = cnt;
if(hson[x]) {
dfs_2(hson[x], a);
} else {
return;
}
for(auto v : G[x]) {
if(v != fa[x] && v != hson[x]) {
dfs_2(v, v);
}
}
}
int n;
void update(int x, int y, const ll &delta) {
if(top[x] == top[y]) {
if(dfn[x] > dfn[y]) std::swap(x, y);
ql = dfn[x], qr = dfn[y]; v = delta;
modify(1, 1, n); return;
}
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
ql = dfn[top[x]], qr = dfn[x]; v = delta;
modify(1, 1, n);
update(fa[top[x]], y, delta);
}
ll query(int x, int y) {
if(top[x] == top[y]) {
if(dfn[x] > dfn[y]) std::swap(x, y);
ql = dfn[x], qr = dfn[y];
return query(1, 1, n);
}
if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
ql = dfn[top[x]], qr = dfn[x];
ll ret = query(1, 1, n);
return (ret + query(fa[top[x]], y)) % ha;
}
struct Q {
int l, z;
int id; ll p;
bool operator <(const Q &res) const {
if(l == res.l) {
return id < res.id;
} else {
return l < res.l;
}
}
};
Q que[maxn << 1];
ll ans[maxn];
int main() {
int q; scanf("%d%d", &n, &q);
for(int i = 2; i <= n; i ++) {
int f; scanf("%d", &f); f ++;
add_edge(f, i);
}
dfs_1(1); dfs_2(1, 1);
for(int i = 1; i <= q; i ++) {
int l, r, z; scanf("%d%d%d", &l, &r, &z);
l ++; r ++; z ++;
Q &L = que[i * 2 - 1]; Q &R = que[i * 2];
L.id = R.id = i; L.p = -1; R.p = 1;
L.z = R.z = z; L.l = l - 1; R.l = r;
}
std::sort(que + 1, que + 1 + 2 * q);
int p = 0;
for(int i = 1; i <= 2 * q; i ++) {
const Q &t = que[i];
while(p < t.l) {
p ++; update(1, p, 1);
}
ans[t.id] = (ans[t.id] + t.p * query(1, t.z) + ha) % ha;
}
for(int i = 1; i <= q; i ++) {
printf("%lld\n", ans[i]);
}
return 0;
}
[LibreOJ 2137][ZJOI2015]诸神眷顾的幻想乡
复习SAM了呢~
那个度数为1的点至多有20个的条件非常神奇……让我们想想怎么用。
我们发现，（钦定根后）在树上有一条路径是弯的这种情况非常不好统计，但如果是直着下来就很好说（把所有从根到一个点的路径扔到SAM里，然后是经典题）。但是，任何一条路一定会在某个度数为1的点为根的情况下是直的（可以意会一下吧（逃
然后我们从那20个点每个点当根DFS一遍，把搞出来的每一条从根开始的路径放前缀Trie里。然后对前缀Trie构一个SAM就行啦~
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
const int BUFSIZE = 128 * 1024 * 1024;
char buf[BUFSIZE];
void *alloc(size_t size) {
static char *cur = buf;
if(cur - buf + size > BUFSIZE) {
return malloc(size);
} else {
char *ret = cur; cur += size;
return ret;
}
}
const int maxn = 100005;
std::vector<int> G[maxn];
int deg[maxn];
int ssiz;
struct TNode {
TNode *ch[10];
};
TNode *alloc_tn() {
auto ret = (TNode*)alloc(sizeof(TNode));
memset(ret -> ch, 0, sizeof(ret -> ch));
return ret;
}
TNode *step(TNode *o, int c) {
if(!(o -> ch[c])) {
o -> ch[c] = alloc_tn();
}
return (o -> ch[c]);
}
TNode *trt;
int col[maxn];
void dfs(int x, int fa, TNode *last) {
TNode *np = step(last, col[x]);
for(auto v : G[x]) {
if(v != fa) {
dfs(v, x, np);
}
}
}
struct Node {
int len; Node *fa;
Node *ch[10];
};
std::vector<Node*> pool;
Node *alloc_node(int len = 0, Node *fa = NULL) {
Node *ret = (Node*)alloc(sizeof(Node));
ret -> len = len; ret -> fa = fa;
memset(ret -> ch, 0, sizeof(ret -> ch));
pool.push_back(ret);
return ret;
}
Node *rt;
Node *extend(int c, Node *last) {
Node *np = alloc_node(last -> len + 1);
Node *p = last;
while(p != NULL && p -> ch[c] == NULL) {
p -> ch[c] = np; p = p -> fa;
}
if(p == NULL) {
np -> fa = rt;
} else {
Node *q = p -> ch[c];
if(q -> len == p -> len + 1) {
np -> fa = q;
} else {
Node *nq = alloc_node(p -> len + 1, q -> fa);
memcpy(nq -> ch, q -> ch, sizeof(q -> ch));
q -> fa = np -> fa = nq;
while(p != NULL && p -> ch[c] == q) {
p -> ch[c] = nq; p = p -> fa;
}
}
}
return np;
}
void dfs_2(TNode *o, Node *last) {
for(int i = 0; i < ssiz; i ++) {
TNode *v = o -> ch[i];
if(!v) continue;
Node *np = extend(i, last);
dfs_2(v, np);
}
}
using ll = long long;
int main() {
int n; scanf("%d%d", &n, &ssiz);
for(int i = 1; i <= n; i ++) {
scanf("%d", &col[i]);
}
trt = alloc_tn();
for(int i = 1; i <= n - 1; i ++) {
int u, v; scanf("%d%d", &u, &v);
G[u].push_back(v); G[v].push_back(u);
deg[u] ++; deg[v] ++;
}
for(int i = 1; i <= n; i ++) {
if(deg[i] == 1) {
dfs(i, 0, trt);
}
}
rt = alloc_node();
dfs_2(trt, rt);
ll ans = 0;
for(auto p : pool) {
if(p -> fa) {
ans += p -> len - p -> fa -> len;
}
}
printf("%lld\n", ans);
return 0;
}
[LibreOJ 2034][SDOI2016]排列计数
我这种池沼只会做水题陶冶身心了……
考虑用\(f_i\)表示长为\(i\)的完全错位全排列的个数，那么有\(i\)个错位的长度为\(n\)的全排列的数量就是\(\binom{n}{i} f_i\)。从这一点出发，可以得到一个式子（枚举错位的有几个）：
\[n! = \sum_{i = 0}^n \binom{n}{i} f_i\]
考虑使用二项式反演，得到：
\[
\begin{aligned}
f_n &= \sum_{i = 0}^n (-1)^{n - i}\binom{n}{i} i!\\
&= \sum_{i = 0}^n (-1)^{n - i}\frac{n!}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^{n - i}}{(n - i)!}\\
&= n!\sum_{i = 0}^n \frac{(-1)^i}{i!}
\end{aligned}
\]
后面的和式可以预处理，然后就做完啦~
代码：
#include <cstdio>
#include <cstring>
using ll = long long;
const ll ha = 1000000007LL;
inline ll pow_mod(const ll &a, ll b) {
ll ans = 1LL, res = a;
while(b) {
if(1LL & b) ans = (ans * res) % ha;
res = (res * res) % ha;
b >>= 1;
}
return ans;
}
inline ll inv(ll x) {
return pow_mod(x, ha - 2LL);
}
const int N = 1000000;
const int maxn = N + 5;
ll fac[maxn], f[maxn];
inline void process() {
fac[0] = 1LL;
for(int i = 1; i <= N; i ++) {
fac[i] = (fac[i - 1] * (ll(i))) % ha;
}
for(int i = 0; i <= N; i ++) {
f[i] = (i % 2 == 1) ? (ha - 1LL) : 1LL;
f[i] = (f[i] * inv(fac[i])) % ha;
if(i > 0) f[i] = (f[i - 1] + f[i]) % ha;
}
}
int main() {
process();
int T; scanf("%d", &T);
while(T --) {
int n, m; scanf("%d%d", &n, &m);
int p = n - m;
ll bs = (fac[p] * f[p]) % ha;
ll C = (fac[n] * inv((fac[p] * fac[m]) % ha)) % ha;
printf("%lld\n", (bs * C) % ha);
}
return 0;
}
[LibreOJ 6024]XLkxc
拉格朗日插值的模板题qwq
考虑\(f(n) = \sum_{i = 1}^n i^k\)，这显然是一个\(k + 1\)次多项式（通过差分之类的手段可以证明），然后我们发现\(g(n) = \sum_{i = 1}^n f(n)\)可以用类似手段证明是\(k + 2\)次多项式。类似的，我们会发现，答案是一个\(k + 3\)次多项式。
分别对\(g\)以及答案插值即可。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <climits>
typedef long long ll;
const ll ha = 1234567891LL;
int k;
ll a, n, d;
ll pf[205], pg[205], fac[205];
ll pow_mod(const ll &a, ll b) {
if(!b) return 1LL;
ll ans = pow_mod(a, b >> 1);
ans = (ans * ans) % ha;
if(b & 1LL) ans = (ans * a) % ha;
return ans;
}
ll inv(ll v) {
return pow_mod(v, ha - 2LL);
}
void process() {
fac[0] = 1LL;
for(int i = 1; i <= k + 5; i ++) {
fac[i] = (fac[i - 1] * inv(i)) % ha;
#ifdef LOCAL
printf("fac[%d] : %lld\n", i, fac[i]);
#endif
}
for(int i = 1; i <= k + 3; i ++) {
pf[i] = (pf[i - 1] + pow_mod(i, k)) % ha;
#ifdef LOCAL
printf("pf[%d] : %lld\n", i, pf[i]);
#endif
}
for(int i = 1; i <= k + 3; i ++) {
pg[i] = (pg[i - 1] + pf[i]) % ha;
#ifdef LOCAL
printf("pg[%d] : %lld\n", i, pg[i]);
#endif
}
#ifdef LOCAL
puts("Processing finished!");
#endif
}
ll g(ll x) {
static ll sim_f[205], sim_g[205];
sim_f[0] = 1LL;
for(int i = 1; i <= k + 3; i ++) {
sim_f[i] = (x - (ll(i)) + ha) % ha;
sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha;
}
sim_g[k + 4] = 1LL;
for(int i = k + 3; i >= 1; i --) {
sim_g[i] = (x - (ll(i)) + ha) % ha;
sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha;
}
ll ret = 0;
for(int i = 1; i <= k + 3; i ++) {
ll ans = (((pg[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha;
ans = (ans * fac[i - 1]) % ha;
ans = (ans * fac[k + 3 - i]) % ha;
if(1 & (k + 3 - i)) {
ret = (ret - ans + ha) % ha;
} else {
ret = (ret + ans) % ha;
}
}
#ifdef LOCAL
printf("g(%lld) : %lld\n", x, ret);
#endif
return ret;
}
ll h(ll x) {
static ll ph[205];
ph[0] = g(a);
for(int i = 1; i <= k + 4; i ++) {
ph[i] = (ph[i - 1] + g(a + (ll(i)) * d)) % ha;
}
static ll sim_f[205], sim_g[205];
sim_f[0] = 1LL;
for(int i = 1; i <= k + 4; i ++) {
sim_f[i] = (x - (ll(i)) + ha) % ha;
sim_f[i] = (sim_f[i] * sim_f[i - 1]) % ha;
}
sim_g[k + 5] = 1LL;
for(int i = k + 4; i >= 1; i --) {
sim_g[i] = (x - (ll(i)) + ha) % ha;
sim_g[i] = (sim_g[i] * sim_g[i + 1]) % ha;
}
ll ret = 0;
for(int i = 1; i <= k + 4; i ++) {
ll ans = (((ph[i] * sim_f[i - 1]) % ha) * sim_g[i + 1]) % ha;
ans = (ans * fac[i - 1]) % ha;
ans = (ans * fac[k + 4 - i]) % ha;
if(1 & (k + 4 - i)) {
ret = (ret - ans + ha) % ha;
} else {
ret = (ret + ans) % ha;
}
}
return ret;
}
int main() {
int T; scanf("%d", &T);
while(T --) {
scanf("%d%lld%lld%lld", &k, &a, &n, &d);
process();
printf("%lld\n", h(n));
}
return 0;
}
[LibreOJ 2249][NOI2014]购票
在紧张刺激的等待之后终于肝掉了这道题……
本题的DP方程长成这样（其中\(a\)指\(v\)的某个满足距离限制的祖先，\(d_v\)指\(v\)到根的路径长）：
\[f_v = min(f_a + p_v(d_v - d_a) + q_v)\]
化简之后发现：
\[f_v = q_v + p_v d_v + min(f_a - p_v d_a)\]
利用\(min\)中那一块很容易发现是截距式……但是问题在于，我们的转移来源是树上的连续一段祖先，怎样维护他们的凸包？
答案很狂暴啊……用树链剖分套上向量集那题的线段树套凸包，然后完了……
（注意一点细节：本题因为数据范围过大，故可能存在两个向量叉乘爆long long，所以在求凸包时如果直接用叉积判断是否需要删点会炸掉，建议用斜率判断）
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <climits>
using ll = long long;
using T = ll;
using R = long double;
const R eps = 1e-8;
int sign(R x) {
if(fabsl(x) < eps) {
return 0;
} else {
if(x > (R(0.00))) {
return 1;
} else {
return -1;
}
}
}
struct Point {
T x, y;
Point(T qx = 0LL, T qy = 0LL) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator *(const Vector &a, T lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(T lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline T dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline T times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if(a.x == b.x) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline R slope(const Vector &a) {
R dx = a.x, dy = a.y;
return (dy / dx);
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && (P[i].x == P[i - 1].x)) continue;
while(bot.size() > 1 && sign(slope(P[i] - bot.back()) - slope(bot.back() - bot[bot.size() - 2])) <= 0) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && (P[i].x == P[i + 1].x)) continue;
while(top.size() > 1 && sign(slope(P[i] - top.back()) - slope(top.back() - top[top.size() - 2])) <= 0) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 200005;
const int maxno = maxn << 2;
const int N = 200000;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline T calc_ans(T k, const Point &v) {
return v.y - k * v.x;
}
inline T search(const std::vector<Point> &vec, const T &k) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if((calc_ans(k, vec[lm]) > calc_ans(k, vec[rm]))) {
l = lm;
} else {
r = rm;
}
}
T ans = LLONG_MAX;
for(int i = l; i <= r; i ++) {
ans = std::min(ans, calc_ans(k, vec[i]));
}
return ans;
}
T query(int o, int L, int R, const int &ql, const int &qr, const T &k) {
if(ql <= L && R <= qr) {
return search(bot[o], k);
} else {
int M = (L + R) / 2;
T ans = LLONG_MAX;
if(ql <= M) {
ans = std::min(ans, query(o << 1, L, M, ql, qr, k));
}
if(qr > M) {
ans = std::min(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
}
return ans;
}
}
int first[maxn];
int next[maxn << 1], to[maxn << 1];
ll dist[maxn << 1];
void add_edge(int u, int v, ll d) {
static int cnt = 0;
cnt ++;
next[cnt] = first[u];
first[u] = cnt;
to[cnt] = v;
dist[cnt] = d;
}
int fa[maxn], dep[maxn], hson[maxn];
ll d[maxn];
int siz[maxn];
int bs[maxn][18];
void dfs_1(int x, int f = -1, int depth = 1) {
fa[x] = bs[x][0] = f; dep[x] = depth;
siz[x] = 1;
int max_siz = 0;
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != f) {
d[v] = d[x] + dist[i];
dfs_1(v, x, depth + 1);
siz[x] += siz[v];
if(siz[v] > max_siz) {
hson[x] = v; max_siz = siz[v];
}
}
}
}
int dfn[maxn], tid[maxn], up[maxn];
void dfs_2(int x, int a = 1, int f = 0) {
static int cnt = 0;
dfn[x] = ++ cnt; tid[cnt] = x;
up[x] = a;
if(hson[x]) {
dfs_2(hson[x], a, x);
} else {
return;
}
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
if(v != f && v != hson[x]) {
dfs_2(v, v, x);
}
}
}
int k_anc(int x, ll k) {
int yx = x;
for(int j = 17; j >= 0; j --) {
int a = bs[x][j];
if(a != -1 && d[yx] - d[a] <= k) {
x = a;
}
}
#ifdef LOCAL
printf("%d's %lld-th anc : %d\n", yx, k, x);
#endif
return x;
}
int n;
ll get_up(int x, int anc, ll k) {
ll ans = LLONG_MAX;
while(up[x] != up[anc]) {
ans = std::min(ans, query(1, 1, n, dfn[up[x]], dfn[x], k));
x = fa[up[x]];
}
return std::min(ans, query(1, 1, n, dfn[anc], dfn[x], k));
}
ll p[maxn], q[maxn], l[maxn];
ll f[maxn];
void dp(int x) {
#ifdef LOCAL
printf("processing %d...\n", x);
printf("d : %lld\n", d[x]);
#endif
if(x != 1) {
#ifdef LOCAL
printf("b : %lld\n", get_up(fa[x], k_anc(x, l[x]), p[x]));
#endif
f[x] = get_up(fa[x], k_anc(x, l[x]), p[x]) + d[x] * p[x] + q[x];
} else {
f[x] = 0;
}
#ifdef LOCAL
printf("ans : %lld\n", f[x]);
#endif
modify(1, 1, n, dfn[x], Point(d[x], f[x]));
for(int i = first[x]; i; i = next[i]) {
int v = to[i];
dp(v);
}
}
int main() {
int t; scanf("%d%d", &n, &t);
for(int i = 2; i <= n; i ++) {
int father; T s;
scanf("%d%lld%lld%lld%lld", &father, &s, &p[i], &q[i], &l[i]);
add_edge(father, i, s);
}
memset(bs, -1, sizeof(bs));
dfs_1(1); dfs_2(1);
for(int j = 1; (1 << j) < n; j ++) {
for(int i = 1; i <= n; i ++) {
int a = bs[i][j - 1];
if(a != -1) {
bs[i][j] = bs[a][j - 1];
}
}
}
dp(1);
for(int i = 2; i <= n; i ++) {
printf("%lld\n", f[i]);
}
return 0;
}
[LibreOJ 2353][NOI2007]货币兑换
emmm做了一下这道神题……（我可能是少有的用动态凸包苟的？）
首先DP方程长这样：
\[f_i = max(f_{i - 1}, f_j\cdot\frac{A_iR_j+B_i}{A_jR_j+B_j})\]
然后这个方程炒鸡复杂……首先\(f_{i - 1}\)不要管了，然后设\(a_i = \frac{f_i}{A_iR_i + B_i}\)。在xjb推了一番之后我们终于得到了截距式……
\[-a_j R_j \frac{A_i}{B_i} + \frac{f_i}{B_i} = a_j\]
但是这玩意太毒瘤了……斜率不可能单调的，这还好，在凸壳上二分/三分一下即可。但问题在于，横坐标也不单调……
这个时候就需要动态维护凸包了（其实是我不会CDQ），我直接把我向量集那题的二进制分组线段树搬了过来……（逃
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <climits>
#include <deque>
#include <cassert>
using R = double;
const R eps = 1e-8;
int sign(R x) {
if(fabs(x) < eps) {
return 0;
} else {
if(x > 0.00) {
return 1;
} else {
return -1;
}
}
}
struct Point {
R x, y;
Point(R qx = 0, R qy = 0) {
x = qx; y = qy;
}
};
using Vector = Point;
Vector operator +(const Vector &a, const Vector &b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator -(const Point &a, const Point &b) {
return Vector(b.x - a.x, b.y - a.y);
}
Vector operator *(const Vector &a, R lam) {
return Vector(a.x * lam, a.y * lam);
}
Vector operator *(R lam, const Vector &a) {
return Vector(a.x * lam, a.y * lam);
}
inline R dot(const Vector &a, const Vector &b) {
return (a.x * b.x + a.y * b.y);
}
inline R times(const Vector &a, const Vector &b) {
return (a.x * b.y - a.y * b.x);
}
inline bool cmp(const Point &a, const Point &b) {
if(sign(a.x - b.x) == 0) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
inline void andrew(Point *P, int L, std::vector<Point> &bot, std::vector<Point> &top) {
std::sort(P + 1, P + 1 + L, cmp);
for(int i = 1; i <= L; i ++) {
if(i != 1 && sign(P[i].x - P[i - 1].x) == 0) continue;
while(bot.size() > 1 && sign(times(P[i] - bot.back(), bot.back() - bot[bot.size() - 2])) >= 0) {
bot.pop_back();
}
bot.push_back(P[i]);
}
for(int i = L; i >= 1; i --) {
if(i != L && sign(P[i].x - P[i + 1].x) == 0) continue;
while(top.size() > 1 && sign(times(P[i] - top.back(), top.back() - top[top.size() - 2])) >= 0) {
top.pop_back();
}
top.push_back(P[i]);
}
std::reverse(top.begin(), top.end());
}
const int maxn = 1000005;
const int N = 1000000;
const int maxno = maxn << 2;
bool zen[maxno];
std::vector<Point> bot[maxno], top[maxno];
Point P[maxn];
inline void maintain(int o, int L, int R) {
static Point tmp[maxn];
const int lc = o << 1, rc = o << 1 | 1;
const bool used = zen[o];
zen[o] = (zen[lc] && zen[rc]);
if(zen[o] != used) {
std::copy(P + L, P + R + 1, tmp + 1);
int len = R - L + 1;
andrew(tmp, len, bot[o], top[o]);
}
}
void modify(int o, int L, int R, const int &p, const Point &v) {
if(L == R) {
zen[o] = true;
P[L] = v;
bot[o].push_back(v); top[o].push_back(v);
} else {
const int M = (L + R) / 2;
if(p <= M) {
modify(o << 1, L, M, p, v);
} else {
modify(o << 1 | 1, M + 1, R, p, v);
}
maintain(o, L, R);
}
}
inline R calc_ans(R k, const Point &v) {
return v.y - k * v.x;
}
inline R search(const std::vector<Point> &vec, const R &k) {
int l = 0, r = vec.size() - 1;
while(r - l > 2) {
int lm = (l * 2 + r) / 3, rm = (2 * r + l) / 3;
if(sign(calc_ans(k, vec[lm]) - calc_ans(k, vec[rm])) == 1) {
r = rm;
} else {
l = lm;
}
}
R ans = INT_MIN;
for(int i = l; i <= r; i ++) {
ans = std::max(ans, calc_ans(k, vec[i]));
}
return ans;
}
R query(int o, int L, int R, const int &ql, const int &qr, const double &k) {
if(ql <= L && R <= qr) {
return search(top[o], k);
} else {
int M = (L + R) / 2;
double ans = INT_MIN;
if(ql <= M) {
ans = std::max(ans, query(o << 1, L, M, ql, qr, k));
}
if(qr > M) {
ans = std::max(ans, query(o << 1 | 1, M + 1, R, ql, qr, k));
}
return ans;
}
}
int n, s;
R A[maxn], B[maxn], Rate[maxn];
R f[maxn];
R dp() {
static double a[maxn];
f[0] = s; f[1] = s; a[1] = f[1] / (A[1] * Rate[1] + B[1]);
modify(1, 1, n, 1, Point(a[1] * Rate[1], a[1]));
for(int i = 2; i <= n; i ++) {
f[i] = query(1, 1, n, 1, i - 1, -A[i] / B[i]) * B[i];
f[i] = std::max(f[i], f[i - 1]);
a[i] = f[i] / (A[i] * Rate[i] + B[i]);
if(i < n) modify(1, 1, n, i, Point(a[i] * Rate[i], a[i]));
}
return f[n];
}
int main() {
scanf("%d%d", &n, &s);
for(int i = 1; i <= n; i ++) {
scanf("%lf%lf%lf", &A[i], &B[i], &Rate[i]);
}
printf("%.3lf\n", dp());
return 0;
}
