摆(行列式、杜教筛)

2024-02-19 20:44
文章标签 行列式 杜教

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

有一个 n × n n\times n n×n 的矩阵 A A A,满足:
A i , j = { 1 i = j 0 i ≠ j ∧ i ∣ j C otherwise A_{i,j}=\begin{cases} 1 &i=j\\ 0 &i\not=j\land i\mid j\\ C &\text{otherwise} \end{cases} Ai,j= 10Ci=ji=jijotherwise

det ⁡ ( A ) \det(A) det(A)。答案模 998244353 998244353 998244353

n ≤ 1 0 11 n\le10^{11} n1011


显然当 C = 0 C=0 C=0 时答案为 1 1 1,当 C = 1 C=1 C=1 时若 n ≤ 2 n\le2 n2 则答案为 1 1 1 否则为 0 0 0

首先 A A A 形如:
[ 1 0 0 0 0 … C 1 C 0 C … C C 1 C C … C C C 1 C … C C C C 1 … ⋮ ⋮ ⋮ ⋮ ⋮ ⋱ ] \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} 1CCCC01CCC0C1CC00C1C0CCC1

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

这里有个式子

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)xnS

其中 B S B_S BS 表示把矩阵 A A A 主对角线元素换成 C C C,只选出行列都在 S S 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}= CCCCC0CCCC00CCC0CCCC000CC

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

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

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

r = C 1 − C r=\frac{C}{1-C} r=1CC,于是 det ⁡ ( A ) = ( 1 − C ) n ∑ S 中元素两两整除 r ∣ S ∣ \det(A)=(1-C)^n\sum\limits_{S中元素两两整除} r^{|S|} det(A)=(1C)nS中元素两两整除rS

f i f_i fi 表示所有满足 S S S 中最大元素为 i i i r ∣ S ∣ r^{|S|} rS 之和(特别地, f 1 = 1 + r f_1=1+r f1=1+r)。容易得到转移式子
f i = r ∑ j ∣ i , j < i f j f_i=r\sum\limits_{j\mid i,j<i}f_j fi=rji,j<ifj

s ( i ) = ∑ j = 1 i f j s(i)=\sum\limits_{j=1}^if_j s(i)=j=1ifj,我们要求出 s ( n ) s(n) s(n)

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

到此直接按式子求答案是 O ( n 3 4 ) O(n^{\frac34}) O(n43) 的,如果预处理出前 n 2 3 n^{\frac23} n32 s ( n ) s(n) s(n),求值可以做到 O ( n 2 3 ) O(n^{\frac23}) O(n32)

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

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

总的时间复杂度为 O ( n 2 3 ) O(n^{\frac23}) O(n32)

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

这篇关于摆(行列式、杜教筛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/725906

相关文章

【高等代数笔记】(18)N阶行列式

2. N阶行列式 2.12 行列式按k行(列)展开 【拉普拉斯定理】 n n n阶矩阵 A = ( a i j ) \boldsymbol{A}=(a_{ij}) A=(aij​),取定第 i 1 , i 2 , . . . , i k i_{1},i_{2},...,i_{k} i1​,i2​,...,ik​行(其中 i 1 < i 2 < . . . < i k i_{1}<i_{2}<.

线性代数行列式概念的引进

1 二阶行列式: 求这个方程组的解。 我们一般是用高斯消元法解这个方程组的。 为了记忆,我们引进记号(其实行列式刚开始,就是为了方便记忆): 二阶行列式: 用高斯消元法求得的解可以表示为如下: 2 三阶行列式: 1) 六项的代数和。恰好是1,2,3这三个数的全排列的个数。 2) 每项都是3个元素的乘积,分析这3个元素的下标:他们取自不同行不

《高等代数》行(列)和相等行列式

说明:此文章用于本人复习巩固,如果也能帮助到大家那就更加有意义了。 注:1)行(列)和相等行列式的求解方法是将其于行都加到第一行(列),然后再提取第一行                 (列),使得第一行(列)变成“1”,再用第一行(列)将行列式化为三角形行列式。

《高等代数》范德蒙德行列式的应用

说明:此文章用于本人复习巩固,如果也能帮助到大家那就更加有意义了。 注:范德蒙德行列式的简单应用及其变形。 范德蒙德行列式的计算公式: 注:(1)用大下标减去小下标。        (2)i>j,不是i≥j 例一:(公式的简单应用) 例二:(缺失的范德蒙德行列式一) 注:1)可以看到,所要求的行列式与范德蒙德行列式相比缺失了次数为三次方的一行。利用行列

《高等代数》两条线行列式

说明:此文章用于本人复习巩固,如果也能帮助到大家那就更加有意义了。 注:两条线行列式的固定做法为按照第一列展开。

《高等代数》“爪”字型行列式

说明:此文章用于本人复习巩固,如果也能帮助到大家那就更加有意义了。 注:1)“爪”字型行列式的第一种求解方法是利用初等行(列)变换,将第一列除第一行的第                 一个数以外的其它数都化为0,得到三角行列式,然后进行求解。        2)“爪”字型行列式的第二种求解方法是“加边法”,其目的也是最终将行列式化为三角行列式           进行求解。

行列式的计算(矩阵外面加个绝对值)

1、写在前面 我表示很难过,曾经线代,矩阵学的也不算太差,可惜太久没用,导致现在连最基本的行列式都不会了。以后还是要多用,多用,多用,重要的事情说三遍。 2、行列式的计算准则 定义:n阶行列式 等于所有取自不同行不同列的n个元素的乘积 的代数和,这里是1,2,...,n的一个排列,每一项都按下列规则带有符号:当是偶排列时带有正号,当是奇排列时带有负号。这一定义可写成 这里表

【解析几何笔记】6.三阶行列式

6. 三阶行列式 6.1 三阶行列式的定义 对三阶方阵 ( a 1 a 2 a 3 b 1 b 2 b 3 c 1 c 2 c 3 ) \begin{pmatrix} a_{1} & a_{2} & a_{3}\\ b_{1} & b_{2} & b_{3}\\ c_{1} & c_{2} &c_{3} \end{pmatrix} ​a1​b1​c1​​a2​b2​c2​​a3​b3​c

洛谷 P10584 [蓝桥杯 2024 国 A] 数学题(整除分块+杜教筛)

题目 思路来源 登录 - Luogu Spilopelia 题解 参考了两篇洛谷题解,第一篇能得出这个式子,第二篇有比较严格的复杂度分析 结合去年蓝桥杯洛谷P9238,基本就能得出这题的正确做法 代码 #include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<map>#include<uno

行列式和矩阵的区别

目录 一、行列式 1. 行列式的定义 2. (全)排列 3. 逆序数 二、矩阵 1. 矩阵的定义 三、行列式和矩阵的区别 四、参考书目 一、行列式 1. 行列式的定义 2. (全)排列 3. 逆序数 二、矩阵 1. 矩阵的定义 三、行列式和矩阵的区别 四、参考书目 同济大学数学系. 工程数学 线性代数 第六版. 高等教育