「SOL」行列式 (模擬賽)

#NOI模擬賽# 『主要內(nèi)容：行列式 / 樹(shù)形DP』

1. 題面

有一個(gè)大小為 \(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\) 的行列式對(duì) \((10^9+7)\) 取模的結(jié)果。

2. 解析

2.1. 拆分矩陣

和另外一道題很像……方陣的大多數(shù)位置都是 \(x\)，可以想到分離出一個(gè)全為 \(x\) 的方陣 \(B\) ——

\[A=A'+B \]

于是可以得到一個(gè)稀疏方陣 \(A'\)。

考慮行列式 \(|M|\) 的定義：枚舉一個(gè)排列 \((q_1,q_2,\dots,q_n)\)，貢獻(xià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. 樹(shù)的情況

不妨先假設(shè) \(x=0\)，則只考慮 \(A'\) 對(duì)行列式的貢獻(xiàn)。根據(jù)題意，\(A'\) 是個(gè)有值的位置關(guān)于主對(duì)角線對(duì)稱的方陣，這像什么？一棵樹(shù)的鄰接表？具體的說(shuō)，是一棵每條邊都有正反向且每個(gè)點(diǎn)有自環(huán)的“樹(shù)”。

于是我們嘗試把行列式的求解搬到樹(shù)上來(lái)。行列式計(jì)算時(shí)可以看作每行每列恰好選一個(gè)元素，那么選擇的 \(A'_{i,q_i}\) 相當(dāng)于選擇了樹(shù)上的一條邊，由于每行每列恰選一個(gè)元素，所以每個(gè)點(diǎn)的出入度都為 \(\mathbf1\) —— 每個(gè)點(diǎn)都屬于一個(gè)簡(jiǎn)單有向環(huán)。

這樣的“樹(shù)”上，有向環(huán)只可能是父親與兒子的二元環(huán)以及自環(huán)。我們可以做一個(gè)樹(shù)形 DP 來(lái)把每個(gè)點(diǎn)劃分到一個(gè)環(huán)中并計(jì)算貢獻(xiàn)。但還有一個(gè)問(wèn)題，行列式還有 \((-1)^{\pi(q)}\) 的系數(shù)，需要進(jìn)行一些轉(zhuǎn)化。

\(\pi(q)\) 的奇偶性和「交換任意兩個(gè)數(shù)，將 \(q\) 變?yōu)橛行虻牟僮鞔螖?shù)」的奇偶性相同。考慮在樹(shù)上合法的排列 \(q\) 的性質(zhì)，我們剛才提到把樹(shù)劃分成若干個(gè)環(huán)，環(huán)在排列（這里用一下置換里的一些定義）里就是一個(gè)循環(huán)。要把一個(gè)排列操作為有序只需要讓它的每個(gè)循環(huán)都有序，注意到一個(gè)長(zhǎng)為 \(L\) 的循環(huán)我們可以通過(guò) \(L-1\) 次操作把它變?yōu)橛行颍凰?\(\pi(q)\) 的奇偶性就和「偶環(huán)個(gè)數(shù)」的奇偶性相同。

更進(jìn)一步的，\(\pi(q)\) 的奇偶性和「\(n\) 減去環(huán)個(gè)數(shù)」的奇偶性相同，這樣每新增一個(gè)環(huán)就乘上 \(-1\)，更加方便樹(shù)形 DP。

2.3. 非樹(shù)邊

現(xiàn)在考慮另一個(gè)方陣 \(B\)，同樣把它看成鄰接矩陣，那么它是一個(gè)邊權(quán)為 \(x\) 的完全圖。

觀察行列式的定義式：

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

每個(gè) \((i,q_i)\) 要么選 \(A'\) 要么選 \(B\)。也就是說(shuō)選擇樹(shù)邊時(shí)也可以選擇權(quán)為 \(x\)，也可以選擇全為 \(x\) 的非樹(shù)邊。但是如果考慮非樹(shù)邊，環(huán)的情況就非常復(fù)雜，我們是否需要考慮這些復(fù)雜的情況呢？

接下來(lái)就是一些數(shù)學(xué)的分析，想到這一步可能需要一些經(jīng)驗(yàn)吧……

如果在一個(gè)選擇環(huán)邊的方案中選擇了兩條權(quán)為 \(x\) 的邊（多于兩條則考慮最后兩條），也就是在矩陣上選擇了 \(B_{a,q_a},B_{b,q_b}\)，我們可以“交換”一下，選擇 \(B_{a,q_b},B_{b,q_a}\)。環(huán)的變化如下圖，會(huì)減少一個(gè)環(huán)，意味著貢獻(xiàn)系數(shù)相反：

由于交換操作是可逆的，這兩張圖一一對(duì)應(yīng)，而貢獻(xiàn)系數(shù)相反，會(huì)被抵消。這也是為什么一開(kāi)始要分離出一個(gè)全為 \(x\) 的方陣 \(B\) 的原因 —— 要保證交換過(guò)后的圖存在，既然 \(B\) 形成完全圖，那么這張圖必然存在。

于是我們只需要考慮至多選擇了一條 \(x\) 邊的情況，也即至多選擇一條非樹(shù)邊，這也可以用樹(shù)形 DP 計(jì)算。情況比較復(fù)雜，參考代碼寫(xiě)得比較丑陋，建議自己想……

3. 小結(jié)

矩陣大多數(shù)位置值一樣時(shí)可以拆成一個(gè)稀疏矩陣 \(A'\) 和另一個(gè)值全部相同的矩陣 \(B\)。

求解行列式又多了一個(gè)新方法了 awa：

當(dāng)稀疏矩陣 \(A'\) “特別稀疏”時(shí)可以狀壓 DP；
也可以把矩陣看成鄰接矩陣，此題保證了 \(p_i\lt i\)，所以鄰接矩陣是一棵樹(shù)。

應(yīng)該更注意矩陣的對(duì)稱性，此題 \(A'\) 有值的位置關(guān)于主對(duì)角線對(duì)稱，與鄰接矩陣相似。

4. 參考代碼

點(diǎn)擊展開(kāi)/折疊特別丑的參考代碼

/* 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;
}