n个未知数和n个等式组成的同余方程组: x[i] = k[i] x[p[i]] + b[i] mod 10007 (1≤i≤n), k[i], b[i], x[i] 是[0,10007)内的整数. q个操作: - 询问当前x[a]的解, 无解输出-1, 多解输出-2. - 修改一个等式, 形式依然是 x[i] = k[i] x[p[i]] + b[i] mod 10007.
(1≤n≤3*10^4, 0≤q≤10^5, 时限2秒, 询问事务约占80%) 本题的名称即为 <一个动态树好题>, 也的确是好题. 既然作者说这是一个动态树好题, 就来找找同余方程和动态树的联系.
每一条方程可以用一个二元组(k,b)描述, 不妨看成一次函数 (课本上说k不能等于0, 本文忽略这一限制). 一次函数之间的复合是容易的, 并且函数的复合运算满足结合律. 单位元是(1,0).
对于每一条方程, 将p[i]向i连一条有向边, 则每个结点有且只有一个父亲, 形成一片有向基环森林. 每棵有向基环树中变量的情况都是能确定下来的. 有向基环树与有根树的唯一区别是多了一条由根指向后代的边. 不妨把它砍掉, 然后用LCT维护. 砍掉之前, 将这条方程与原来的等式推导出的方程联立, 解出根结点对应的值, 并保存下来. 这样信息就不会丢失了. 只要支持查询根结点到每个点的函数关系, 再把先前保存的值代入, 就能回答询问. 本段所有 "根结点" 指的是有向树的树根, 不是Splay的树根.
LCT支持链查询的方法是, 通过access+splay操作, 将某点到根的路径装进一棵Splay树, 查询这棵Splay树的信息. 即, 把链的查询转化为子树查询. 对于每个点, 设原本的函数为f, 所在Splay子树的所有f按中序遍历的顺序复合得到g, 维护f,g. 其中f仅在修改操作改变, 空结点和根结点的f=(1,0). 现在, access+splay, g即是根结点到某点的函数关系.
初始化的时候需要link, 修改不妨看成cut和link两个步骤.
设link(x,y,f)添加一个函数: f(x)=y. 若x, y不在同一棵树中, 直接将y的设置为x的非偏爱儿子. 否则, 解出y的值并保存下来, 不对树的形态做改变. 逆元可以预处理.
设cut(x,y)删除原来的函数f(x)=y, 设x, y所在树的树根为r, 被砍掉的r的父亲为p. 如果y=r, 不用改动树的形态. 若y在原有向基环树的环上, 砍掉(x,y), 连上(p,r), 因为原来的解失效了, 但函数关系仍然在; 否则, 只砍掉(x,y). 判断是否在环上的一个方法是看y是否为p或p的祖先, 求lca(p,y)即可. 有根树求lca, 两次access就好. 无论是哪种情况, y都成了树根, 不要忘记先前对树根的约定: f=(1,0), 保存根结点的解 (现在一定变成了多解).
其他题解的方法和我的相似, 不过上述做法常数较小, 不加读入优化bzoj上rank 14, 加了是rank 1.
线性求逆元的方法给个推导:
要求p是素数, 以确保[1,p)逆元存在.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
using namespace std;
const int MOD = 10007, N = 30000;
int inv[MOD];
struct Fun {
int k, b;
Fun(int k=1, int b=0): k(k), b(b) {}
Fun operator*(const Fun& o) const
{
return Fun(k * o.k % MOD, (o.k * b + o.b) % MOD);
}
int operator()(const int x) const
{
return x < 0 ? x : (k*x + b) % MOD;
}
};
struct Equation {
int p;
Fun f;
} E[N + 1];
struct Node {
Node* ch[2], * fa;
int t, x;
Fun f, g;
Node();
void setf(Node* f1, int t1)
{
fa = f1;
t = t1;
t >= 0 ? fa->ch[t] = this : 0;
}
void up()
{
g = ch[0]->g * f * ch[1]->g;
}
} nodes[N + 1], * nil = nodes;
Node::Node(): fa(0), t(-1), x(-2) { ch[0] = ch[1] = nil; }
inline void rot(Node* y)
{
Node* x = y->fa;
int t = y->t;
y->setf(x->fa, x->t);
y->ch[t^1]->setf(x, t);
x->setf(y, t^1);
x->up();
}
void splay(Node* x)
{
Node* y;
while (x->t >= 0) {
if ((y = x->fa)->t >= 0)
rot(x->t ^ y->t ? x : y);
rot(x);
}
x->up();
}
Node* access(Node* x)
{
Node* y;
for (y = nil; x; y = x, x = x->fa) {
splay(x);
x->ch[1]->t = -1;
y->setf(x, 1);
x->up();
}
return y;
}
Node* get_root(Node* x)
{
access(x);
splay(x);
while (x->ch[0] != nil) x = x->ch[0];
return x;
}
Fun get_fun(Node* x)
{
access(x);
splay(x);
return x->g;
}
// f: x -> y
// y is the root of a tree
inline void link(Node* x, Node* y, const Fun& f)
{
Node* rx = get_root(x), * ry = get_root(y);
if (rx == ry) {
Fun yy = get_fun(x) * f;
if (yy.k == 1)
y->x = yy.b ? -1 : -2;
else
y->x = yy.b * inv[(1 + MOD - yy.k) % MOD] % MOD;
} else {
y->f = f;
y->up();
y->setf(x, -1);
}
}
// x->y
inline void cut(Node* x, Node* y)
{
Node* r = get_root(y), * p, * z;
const Equation& e = E[r - nodes];
y->x = -2;
if (r == y) return;
access(p = nodes + e.p);
z = access(y);
splay(y);
y->ch[0]->setf(0, -1);
y->ch[0] = nil;
y->f = Fun();
y->up();
if (z == y) link(p, r, e.f);
}
void init()
{
inv[1] = 1;
Rep (i, 2, MOD)
inv[i] = (MOD - MOD/i) * inv[MOD % i] % MOD;
}
int main()
{
init();
int n;
scanf("%d", &n);
For (i, 1, n) {
scanf("%d%d%d", &E[i].f.k, &E[i].p, &E[i].f.b);
link(nodes + E[i].p, nodes + i, E[i].f);
}
int q;
scanf("%d", &q);
while (q--) {
char op;
int a, k, p, b;
scanf(" %c%d", &op, &a);
if (op == 'A') {
Node* r = get_root(nodes + a);
printf("%d\n", nodes[a].g(r->x));
} else {
scanf("%d%d%d", &k, &p, &b);
cut(nodes + E[a].p, nodes + a);
E[a] = (Equation){p, Fun(k, b)};
link(nodes + p, nodes + a, E[a].f);
}
}
return 0;
}