一道线代题

这学期学习了线性代数，这样打 a 的时候遇到线代终于不坐牢了，但是水平还是不太够，得加训

打杭电时遇到的，问题描述很简单：

\(C_{i,j} = (a_i⊕b_j)(\varphi(a_i)+\varphi(b_i))\)

求 \((\det C)\mod 998244353\)

\(n\leq10^5,a_i,b_i\leq10^7\)

首先考虑一个基础的问题，令 \(D_{i,j} = a_ib_j\)，求 \(rank(D)\)

很显然:

\[D = \begin{pmatrix}a_1 \\a_2 \\... \\a_n \end{pmatrix}\begin{pmatrix} b_1~b_2~...~ b_n \end{pmatrix} \]

考虑 \(D\) 的每一列 \(D_i\) ，均可表示为 \(D_i = kA\)，故 \(rank(D) = 1\)，当且仅当 \(n = 1\) 时，\(\det D \neq 0\)

现在进一步考虑这样的 \(D\), \(D_{i,j} = \sum^k_{p=1} a_{i,p}b_{j,p}\)

此时 \(D\) 的每一行 \(D_j\) 可表示为:

\[D_j = \begin{pmatrix}\sum^k_{p=1} a_{1,p}b_{j,p} \\\sum^k_{p=1} a_{2,p}b_{j,p} \\...\\\sum^k_{p=1} a_{n,p}b_{j,p} \end{pmatrix} = b_{j,1}\begin{pmatrix}a_{1,1} \\a_{2,1} \\... \\a_{n,1} \end{pmatrix} + b_{j,2}\begin{pmatrix}a_{1,2} \\a_{2,2} \\... \\a_{n,2} \end{pmatrix} ... + b_{j,k}\begin{pmatrix}a_{1,k} \\a_{2,k} \\... \\a_{n,k} \end{pmatrix} \]

我们可以看到，对于任意 \(D_j\)，它都是固定的 \(k\) 个列向量的线性组合。

因此对于 \(D\) 的列向量，均可由大小为 \(k\) 的向量组 \(a\) 线性表出，即 \(D\) 的列向量组可由 \(a\) 线性表出。

于是有 \(rank(D) \leq rank(a) \leq k\)。

根据上述分析，我们可以得到一个有用的推论，对于矩阵 \(D\)，若对于所有 \(D_{i,j}\)，均可表示为 \(k\) 个仅与 \(i\) 相关的量和仅与 \(j\) 相关的量的乘积的和，则 \(rank(D)\leq k\)

回到这道题，最直观的线性运算就是加法与数乘，异或在矩阵下并不容易直接处理，故考虑拆位。

\(a_i⊕b_j = \sum_{p=0}^{27} 2^p(a_{i,p}⊕b_{j,p}) = \sum_{p=0}^{27} 2^p(a_{i,p}+b_{j,p}-a_{i,p}b_{j,p})\)

因此：

\[C_{i,j} = \sum_{p=0}^{27}2^p(a_{i,p}+b_{j,p}-a_{i,p}b_{j,p})(\varphi(a_i)+\varphi(b_i)) = (a_i+b_j-\sum_{p=0}^{27}2^pa_{i,p}b_{j,p})(\varphi(a_i)+\varphi(b_i)) \]

我们可以看到，对于每个 \(C_{i,j}\)，其至多被 <=2*2+27*2=58 个形如 \(a_ib_j\) 的项累加表示，因此 \(rank(D)\leq58\)

所以对于所有 \(n>58\) 的 \(D\)，必然有 \(rank(D)<n\)，故 \(\det D\) 必然为 \(0\)

所以只需要对 \(n\leq58\) 的 \(D\) 暴力算行列式即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll mod = 998244353;
const ll N = 5e5+5,V = 1e7+10;
ll n,a[N],b[N],c[111][111];
ll tot,vis[V],pri[V],phi[V];
void init(){phi[1] = 1;for(int i=2;i<=V-10;i++){if(!vis[i]) pri[++tot] = i,phi[i] = i-1;for(int j=1;j<=tot && 1ll*pri[j]*i<=V-10;j++){vis[pri[j]*i] = 1;if(i%pri[j] == 0) {phi[i*pri[j]] = phi[i]*pri[j];break;}phi[i*pri[j]] = phi[i]*phi[pri[j]];}}
}
ll qpow(ll a,ll p){ll res = 1;for(;p;p>>=1,a=a*a%mod) if(p&1) res = res*a%mod;return res;
}
ll calc(){ll ans = 1;for(int i=1;i<=n;i++){int j=i;while(!c[j][i] && j<=n) j++;if(j>n) return 0;swap(c[i],c[j]);ans = ans*c[i][i]%mod;ll inv = qpow(c[i][i],mod-2)%mod;for(int j=i+1;j<=n;j++){ll x = (mod-c[j][i]*inv%mod)%mod;for(int k=i;k<=n;k++){c[j][k] += c[i][k]*x%mod;if(c[j][k]>=mod) c[j][k] -= mod;}}}return ans;
}
void solve(){cin >> n;for(int i=1;i<=n;i++) cin >> a[i];for(int i=1;i<=n;i++) cin >> b[i];if(n>=60){cout << 0 << '\n';return ; }for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c[i][j] = (a[i]^b[j])*(phi[a[i]]+phi[b[j]])%mod;}}cout << calc() << '\n';
}
int main(){cin.tie(0),cout.tie(0);ios::sync_with_stdio(0);int T = 1;cin >> T;init();while(T--) solve();return 0;
}

这题感觉是个不错的模型，应对这种 \(C_{i,j}\) 为 \(i\) 一坨缝上 \(j\) 一坨的形式时，可以考虑把每一项复杂的运算化简为基本的加法和数乘，再用上文的推论减小 \(n\) 的范围。