摆（行列式、杜教筛）

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

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

$n\le 10^{11}$。

---

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

首先 $A$ 形如：
$$\left[\begin{array}{cccccc}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 \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right]$$

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

这里有个式子

det ⁡ ( A ) = ∑ S ⊂ { 1 , 2 , … , n } det ⁡ ( B S ) ⋅ x n − ∣ S ∣ \det(A)=\sum\limits_{S\subset\{1,2,\dots,n\}}\det(B_S)\cdot x^{n-|S|} det(A)=S⊂{1,2,…,n}∑​det(BS​)⋅xn−∣S∣

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

例如： B { 1 , 2 , 4 , 5 , 8 } = [ 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 ] 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} B{1,2,4,5,8}​= ​CCCCC​0CCCC​00CCC​0CCCC​000CC​ ​

证明考虑感性理解。设 $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$ 的系数为 $\left(\genfrac{}{}{0ex}{}{m}{i}\right)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 _{S中元素两两整除}{r}^{|S|}$

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

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

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

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

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

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

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

#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;
}