摆（行列式、杜教筛）

2024-02-19 20:44

文章标签 行列式杜教

本文主要是介绍摆（行列式、杜教筛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有一个 $n\times n$ 的矩阵 $A$ ，满足：
$A_{i,j}=\begin{cases} 1 &i=j\\ 0 &i\not=j\land i\mid j\\ C &\text{otherwise} \end{cases}$

求 $\det(A)$ 。答案模 $998244353$ 。

$n\le10^{11}$ 。

显然当 $C = 0$ 时答案为 $1$ ，当 $C = 1$ 时若 $n\le2$ 则答案为 $1$ 否则为 $0$ 。

首先 $A$ 形如：
$\begin{bmatrix} 1&0&0&0&0&\dots\\ C&1&C&0&C&\dots\\ C&C&1&C&C&\dots\\ C&C&C&1&C&\dots\\ C&C&C&C&1&\dots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{bmatrix}$

考虑把主对角线的 $1$ 换位 $C + x$ ，这样 $\det(A)$ 就可看做关于 $x$ 的多项式，求值只需代入 $x = 1 - C$ 即可。

这里有个式子

$\det(A)=\sum\limits_{S\subset\{1,2,\dots,n\}}\det(B_S)\cdot x^{n-|S|}$

其中 $B_S$ 表示把矩阵 $A$ 主对角线元素换成 $C$ ，只选出行列都在 $S$ 中的元素拼接形成的矩阵。

例如： $B_{\{1,2,4,5,8\}}=\begin{bmatrix} C&0&0&0&0\\ C&C&0&C&0\\ C&C&C&C&0\\ C&C&C&C&C\\ C&C&C&C&C\\ \end{bmatrix}$

证明考虑感性理解。设 $i = n - ∣ S ∣$ ，对于 $x^{i}$ 的系数，考虑行列式的定义，要选出行列都互不相同的 $n$ 个数相乘，由于只有主对角线上的 $C + x$ 有次数贡献，于是考虑选出来 $m$ 个主对角线上的元素（ $m\ge i$ ），剩下的行列拼接在一起后面选。我们此时发现 $n - m + m - i = n - i$ ，说明 $B_S$ 是由 $S$ 的行列与 $m$ 行列之中选 $m - i$ 个组成的， $C+x)^m$ 中 $x^i$ 的系数为 $\binom{m}{i}C^{m-i}$ ，恰好满足条件。

我们观察 $B_S$ ，发现如果 $S$ 中元素两两整除，那么 $B_S$ 是下三角矩阵， $det(B_S)=C^{|S|}$ 。否则可以证明 $det(B_S)=0$ 。

考虑归纳法证明，如果 $S$ 中存在两个数不为 $S$ 中其他任何数的因子，那么矩阵中就会出现两行 $C$ ， $det(B_S)=0$ ；否则 $S$ 中最大的数一定是其他数的倍数，从而只有最后一行全为 $C$ ，不妨删去最后一行列。这样递归下去，容易发现结论成立。

设 $r=\frac{C}{1-C}$ ，于是 $\det(A)=(1-C)^n\sum\limits_{S中元素两两整除} r^{|S|}$

令 $f_i$ 表示所有满足 $S$ 中最大元素为 $i$ 的 $r^{|S|}$ 之和（特别地， $f_1=1+r$ ）。容易得到转移式子
$f_i=r\sum\limits_{j\mid i,j<i}f_j$

令 $s(i)=\sum\limits_{j=1}^if_j$ ，我们要求出 $s (n)$ 。

考虑杜教筛，我们构造 $g(n)=\begin{cases}-1&n=1\\r&n>1\end{cases}$ ，函数 $h = f * g$ ，容易验证 $h(n)=\begin{cases}-r-1&n=1\\0&n>1\end{cases}$ 。套用公式 $g(1)s(n)=\sum\limits_{i=1}^nh_i-\sum\limits_{i=2}^ng(i)s(\lfloor\frac ni\rfloor)$ ，可以得到 $s (n)$ 的转移式子
$s(n)=1+r+r\sum\limits_{i=2}^ns(\lfloor\frac ni\rfloor)$

到此直接按式子求答案是 $O(n^{\frac34})$ 的，如果预处理出前 $n^{\frac23}$ 个 $s (n)$ ，求值可以做到 $O(n^{\frac23})$ 。

但是预处理时间复杂度容易带上 $\log$ ，所以要考虑优化。

设 $n=\prod p_i^{k_i}$ ，如果我们把 $p_1,p_2,\dots$ 依次换成 $2,3,5,7,\dots$ ，所得到的数设为 $n^{'}$ ，容易发现 $f_n=f_{n'}$ 。这启发我们 $f_n$ 的值只与可重集 $k$ 有关。通过暴力发现可重集的数量很少，于是我们可以暴力求出这些“代表”的函数值，然后让找到其他数所对应的“代表”。用欧拉筛实现，具体实现可参照代码。

总的时间复杂度为 $O(n^{\frac23})$ 。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353,N=2e7+1;
ll n,c,R;
int a[N],p[N],cnt,m,to[N],num[N],Max[N];
ll S[N];
unordered_map<ll,int> ma;
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
ll s(ll n)
{if(n<=m) return S[n];if(ma.count(n)) return ma[n];ll ans=1+R;for(ll i=2,r;i<=n;i=r+1){r=n/(n/i);ans=(ans+(r-i+1)%mod*R%mod*s(n/i))%mod;}return ma[n]=ans;
}
void init(int n)
{a[1]=1,to[1]=S[1]=1+R;for(int i=2;i<=n;i++){if(!a[i]){p[++cnt]=i;to[i]=2;num[i]=1;Max[i]=i;}if(to[i]==i){for(int j=1;j*j<=i;j++) if(i%j==0) S[i]=(S[i]+S[j]+(j*j<i&&j>1)*S[i/j])%mod;S[i]=S[i]*R%mod;}else S[i]=S[to[i]];for(int j=1;j<=cnt&&i*p[j]<=n;j++){int x=i*p[j];a[x]=1;Max[x]=Max[i];if(i%p[j]==0){num[x]=num[i];to[x]=to[x/Max[x]]*p[num[x]];break;}num[x]=num[i]+1;to[x]=to[x/Max[x]]*p[num[x]];}}for(int i=2;i<=n;i++) S[i]=(S[i]+S[i-1])%mod;
}
int main()
{freopen("bigben.in","r",stdin);freopen("bigben.out","w",stdout);cin>>n>>c;if(!c) cout<<1,exit(0);if(c==1) cout<<(n<=2),exit(0);R=c*ksm(1-c+mod,mod-2)%mod;init(m=min(n,N-1));cout<<s(n)*ksm(1-c+mod,n)%mod;
}