「SOL」行列式 (模拟赛)

1. 题面

有一个大小为 \(n\)\(n\le10^6\))的方阵 \(A\),给定 \(d_1,d_2,d_3,\dots,d_n\)\((p_2,b_2,c_2),(p_3,b_3,c_3),\dots,(p_n,b_n,c_n)\) 以及 \(x\)。其中保证 \(p_i\lt i\)\(A\) 满足:

\[A_{ij}=\begin{cases}d_i&i=j\\b_i&i=p_j\\c_i&j=p_i\\x&otherwise\end{cases} \]

\(A\) 的行列式对 \((10^9+7)\) 取模的结果。


2. 解析

2.1. 拆分矩阵

和另外一道题很像……方阵的大多数位置都是 \(x\),可以想到分离出一个全为 \(x\) 的方阵 \(B\) ——

\[A=A‘+B \]

于是可以得到一个稀疏方阵 \(A‘\)

考虑行列式 \(|M|\) 的定义:枚举一个排列 \((q_1,q_2,\dots,q_n)\),贡献为 \((-1)^{\pi(q)}\prod M_{i,q_i}\)。这道题就是:

\[\sum_{q}(-1)^{\pi(q)}\prod_{i}(A‘_{i,q_i}+B_{i,q_i}) \]

2.2. 树的情况

不妨先假设 \(x=0\),则只考虑 \(A‘\) 对行列式的贡献。根据题意,\(A‘\) 是个有值的位置关于主对角线对称的方阵,这像什么?一棵树的邻接表?具体的说,是一棵每条边都有正反向且每个点有自环的“树”。

于是我们尝试把行列式的求解搬到树上来。行列式计算时可以看作每行每列恰好选一个元素,那么选择的 \(A‘_{i,q_i}\) 相当于选择了树上的一条边,由于每行每列恰选一个元素,所以每个点的出入度都为 \(\mathbf1\) —— 每个点都属于一个简单有向环

这样的“树”上,有向环只可能是父亲与儿子的二元环以及自环。我们可以做一个树形 DP 来把每个点划分到一个环中并计算贡献。但还有一个问题,行列式还有 \((-1)^{\pi(q)}\) 的系数,需要进行一些转化。

\(\pi(q)\) 的奇偶性和「交换任意两个数,将 \(q\) 变为有序的操作次数」的奇偶性相同。考虑在树上合法的排列 \(q\) 的性质,我们刚才提到把树划分成若干个,环在排列(这里用一下置换里的一些定义)里就是一个循环。要把一个排列操作为有序只需要让它的每个循环都有序,注意到一个长为 \(L\) 的循环我们可以通过 \(L-1\) 次操作把它变为有序;所以 \(\pi(q)\) 的奇偶性就和「偶环个数」的奇偶性相同。

更进一步的,\(\pi(q)\) 的奇偶性和「\(n\) 减去环个数」的奇偶性相同,这样每新增一个环就乘上 \(-1\),更加方便树形 DP。

2.3. 非树边

现在考虑另一个方阵 \(B\),同样把它看成邻接矩阵,那么它是一个边权为 \(x\) 的完全图。

观察行列式的定义式:

\[\sum_{q}(-1)^{\pi(q)}\prod_{i}(A‘_{i,q_i}+B_{i,q_i}) \]

每个 \((i,q_i)\) 要么选 \(A‘\) 要么选 \(B\)。也就是说选择树边时也可以选择权为 \(x\),也可以选择全为 \(x\) 的非树边。但是如果考虑非树边,环的情况就非常复杂,我们是否需要考虑这些复杂的情况呢?

接下来就是一些数学的分析,想到这一步可能需要一些经验吧……

如果在一个选择环边的方案中选择了两条权为 \(x\) 的边(多于两条则考虑最后两条),也就是在矩阵上选择了 \(B_{a,q_a},B_{b,q_b}\),我们可以“交换”一下,选择 \(B_{a,q_b},B_{b,q_a}\)。环的变化如下图,会减少一个环,意味着贡献系数相反:

「SOL」行列式 (模拟赛)

由于交换操作是可逆的,这两张图一一对应,而贡献系数相反,会被抵消。这也是为什么一开始要分离出一个全为 \(x\) 的方阵 \(B\) 的原因 —— 要保证交换过后的图存在,既然 \(B\) 形成完全图,那么这张图必然存在。

于是我们只需要考虑至多选择了一条 \(x\) 边的情况,也即至多选择一条非树边,这也可以用树形 DP 计算。情况比较复杂,参考代码写得比较丑陋,建议自己想……


3. 小结

矩阵大多数位置值一样时可以拆成一个稀疏矩阵 \(A‘\) 和另一个值全部相同的矩阵 \(B\)

求解行列式又多了一个新方法了 awa:

  • 当稀疏矩阵 \(A‘\) “特别稀疏”时可以状压 DP;
  • 也可以把矩阵看成邻接矩阵,此题保证了 \(p_i\lt i\),所以邻接矩阵是一棵树。

应该更注意矩阵的对称性,此题 \(A‘\) 有值的位置关于主对角线对称,与邻接矩阵相似。


4. 参考代码

点击展开/折叠 特别丑的参考代码
/* Lucky_Glass */
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>

const int MOD = 1e9 + 7;

inline int add(int a, const int &b) { return (a += b) >= MOD ? a - MOD : a; }
inline int sub(int a, const int &b) { return (a -= b) < 0 ? a + MOD : a; }
inline int mul(const int &a, const int &b) { return int(1ll * a * b % MOD); }
int pPow(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) r = mul(r, a);
    a = mul(a, a), b >>= 1;
  }
  return r;
}
#define OPERON(a, b, fun) a = fun(a, b)

const int N =  1e6 + 10;

struct Graph {
  int head[N], to[N << 1], nxt[N << 1], val[N << 1];
  int edg_cnt;
  inline void addEdge(const int &u, const int &v, const int &l) {
    int p = ++edg_cnt;
    to[p] = v, val[p] = l;
    nxt[p] = head[u], head[u] = p;
  }
  inline int operator [] (const int &u) const { return head[u]; }
  Graph() { edg_cnt = 1; }
} gr;

int n, valx;
int vald[N];
int f[N][4][2];

void dfs(const int &u, const int &fa) {
  int u_emp[2] = {1, 0}, u_use[2] = {}, u_up[2] = {}, u_dn[2] = {};
  for (int it = gr[u]; it; it = gr.nxt[it]) if (gr.to[it] != fa) {
    int v = gr.to[it]; dfs(v, u);
    int tmp_emp[2] = {}, tmp_use[2] = {}, tmp_up[2] = {}, tmp_dn[2] = {};
    int tov = gr.val[it], tou = gr.val[it ^ 1];

    /* empty + empty */
    OPERON(tmp_emp[0], mul(u_emp[0], f[v][0][0]), add);
    OPERON(tmp_emp[1], mul(u_emp[1], f[v][0][0]), add);
    OPERON(tmp_emp[1], mul(u_emp[0], f[v][0][1]), add);

    /* two-point loop */
    OPERON(tmp_use[0], mul(mul(u_emp[0], f[v][1][0]), mul(tov, tou)), sub);
    OPERON(tmp_use[1], mul(mul(u_emp[1], f[v][1][0]), mul(tov, tou)), sub);
    OPERON(tmp_use[1], mul(mul(u_emp[0], f[v][1][1]), mul(tov, tou)), sub);
    /* used + empty */
    OPERON(tmp_use[0], mul(u_use[0], f[v][0][0]), add);
    OPERON(tmp_use[1], mul(u_use[1], f[v][0][0]), add);
    OPERON(tmp_use[1], mul(u_use[0], f[v][0][1]), add);
    /* up */
    OPERON(tmp_use[1], mul(mul(u_emp[0], f[v][2][0]), mul(valx, tou)), sub);
    /* down */
    OPERON(tmp_use[1], mul(mul(u_emp[0], f[v][3][0]), mul(valx, tov)), sub);
    /* lca */
    OPERON(tmp_use[1], mul(mul(u_up[0], f[v][3][0]), mul(tov, valx)), sub);
    OPERON(tmp_use[1], mul(mul(u_dn[0], f[v][2][0]), mul(tou, valx)), sub);

    /* go up */
    OPERON(tmp_up[0], mul(mul(u_emp[0], f[v][2][0]), tou), add);
    OPERON(tmp_up[1], mul(mul(u_emp[1], f[v][2][0]), tou), add);
    OPERON(tmp_up[1], mul(mul(u_emp[0], f[v][2][1]), tou), add);
    /* up + empty */
    OPERON(tmp_up[0], mul(u_up[0], f[v][0][0]), add);
    OPERON(tmp_up[1], mul(u_up[1], f[v][0][0]), add);
    OPERON(tmp_up[1], mul(u_up[0], f[v][0][1]), add);

    /* go down */
    OPERON(tmp_dn[0], mul(mul(u_emp[0], f[v][3][0]), tov), add);
    OPERON(tmp_dn[1], mul(mul(u_emp[1], f[v][3][0]), tov), add);
    OPERON(tmp_dn[1], mul(mul(u_emp[0], f[v][3][1]), tov), add);
    /* down + empty */
    OPERON(tmp_dn[0], mul(u_dn[0], f[v][0][0]), add);
    OPERON(tmp_dn[1], mul(u_dn[1], f[v][0][0]), add);
    OPERON(tmp_dn[1], mul(u_dn[0], f[v][0][1]), add);

    u_emp[0] = tmp_emp[0], u_emp[1] = tmp_emp[1];
    u_use[0] = tmp_use[0], u_use[1] = tmp_use[1];
    u_up[0] = tmp_up[0], u_up[1] = tmp_up[1];
    u_dn[0] = tmp_dn[0], u_dn[1] = tmp_dn[1];
  }

  /* self loop */
  OPERON(f[u][0][1], mul(u_emp[0], valx), sub);
  OPERON(f[u][0][1], mul(u_emp[1], vald[u]), sub);
  OPERON(f[u][0][0], mul(u_emp[0], vald[u]), sub);
  /* others */
  OPERON(f[u][0][0], u_use[0], add);
  OPERON(f[u][0][1], u_use[1], add);

  /* two-point loop with fa */
  OPERON(f[u][1][0], u_emp[0], add);
  OPERON(f[u][1][1], u_emp[1], add);

  /* go up */
  OPERON(f[u][2][0], u_up[0], add);
  OPERON(f[u][2][1], u_up[1], add);
  /* start from u */
  OPERON(f[u][2][0], u_emp[0], add);
  OPERON(f[u][2][1], u_emp[1], add);

  /* go down */
  OPERON(f[u][3][0], u_dn[0], add);
  OPERON(f[u][3][1], u_dn[1], add);
  /* end at u */
  OPERON(f[u][3][0], u_emp[0], add);
  OPERON(f[u][3][1], u_emp[1], add);
}
template<typename RType> RType rin(RType &r) {
  int b = 1, c = getchar(); r = 0;
  while (c < ‘0‘ || ‘9‘ < c) b = c == ‘-‘ ? -1 : b, c = getchar();
  while (‘0‘ <= c && c <= ‘9‘) r = r * 10 + (c ^ ‘0‘), c = getchar();
  return r *= b;
}
int main() {
  rin(n), rin(valx);
  for (int i = 1; i <= n; ++i) {
    rin(vald[i]);
    OPERON(vald[i], valx, sub);
  }
  for (int i = 2; i <= n; ++i) {
    int fa, tofa, tou;
    rin(fa), rin(tofa), rin(tou);
    OPERON(tofa, valx, sub), OPERON(tou, valx, sub);
    gr.addEdge(i, fa, tofa);
    gr.addEdge(fa, i, tou);
  }

  dfs(1, 0);
  int ans = add(f[1][0][0], f[1][0][1]);
  if (n & 1) ans = sub(0, ans);
  printf("%d\n", ans);
  return 0;
}

THE END

Thanks for reading!

我偏要 让世界都坠落
湮灭前 整个银河繁星闪烁
撕裂哀鸣是最后的挽歌

——《恒星坠落之时(森罗万象)》 By 星尘/赤羽

> Link 恒星坠落之时 - Bilibili

「SOL」行列式 (模拟赛)

上一篇:sql server对并发的处理-乐观锁和悲观锁


下一篇:Vue自定义组件开发:使用v-model封装el-pagination组件