题面
摆
题解
首先我们将原矩阵写成
A
+
B
A+B
A+B，其中
B
B
B 全是
C
C
C，那么
A
A
A 的第
i
i
i 行就只有其倍数处有值，且
A
i
,
i
=
1
?
C
,
A
i
,
j
(
i
∣
j
∧
i
≠
j
)
=
?
C
A_{i,i}=1-C,A_{i,j(i|j\land i\neq j)}=-C
Ai,i?=1?C,Ai,j(i∣j∧i?=j)?=?C。
那么原来的行列式就变成了：
∑
p
(
?
1
)
sgn
?
(
p
)
∑
S
?
{
1
,
?
?
,
n
}
∏
i
∈
S
A
i
,
p
i
∏
i
∈?
S
B
i
,
p
i
\sum_{p}(-1)^{\operatorname{sgn}(p)}\sum_{S\subseteq \{1,\cdots,n\}}\prod_{i\in S}A_{i,p_i}\prod_{i\not\in S}B_{i,p_i}
p∑?(?1)sgn(p)S?{1,?,n}∑?i∈S∏?Ai,pi??i?∈S∏?Bi,pi??
考虑在
A
A
A 中选的点数（
∣
S
∣
|S|
∣S∣），发现它不可能小于
n
?
1
n-1
n?1，否则对于
B
B
B 要求的就是一个大小大于
1
1
1、全是
C
C
C 的矩阵的行列式，它恒为
0
0
0。
那么假设
B
B
B 中选的那个点（
B
B
B 中没选点的情况很好算，略）为
(
i
,
p
i
)
(i,p_i)
(i,pi?)。考虑把行列式问题放在图论上（注意到
(
?
1
)
sgn
?
(
p
)
(-1)^{\operatorname{sgn}(p)}
(?1)sgn(p) 为
(
?
1
)
n
?
环个数
(-1)^{n-\text{环个数}}
(?1)n?环个数，所以系数的问题也是可以处理的），相当于说
B
B
B 在图上钦定了一条边
i
→
p
i
i\to p_i
i→pi? 必须选，那么在
A
A
A 中选的就应该是：
-
p
i
→
?
→
i
p_i\to \cdots\to i
pi?→?→i 的一条链，其中每一条边后者是前者的倍数，且边权为
?
C
-C
?C。
- 发现剩下的点在
A
A
A 中都只能选自环（从大往小推每个点即可），边权为
1
?
C
1-C
1?C。
假设
f
n
f_n
fn? 表示链尾是
n
n
n 的所有方案的和，可以得到：
f
n
=
C
(
1
?
C
)
n
?
1
+
∑
d
∣
n
∧
d
≠
n
C
1
?
C
f
d
f_n=C(1-C)^{n-1}+\sum_{d|n\land d\neq n}\frac{C}{1-C}f_d
fn?=C(1?C)n?1+d∣n∧d?=n∑?1?CC?fd?
其中前者是链长为
1
1
1 的方案，后者是链长大于
1
1
1 的方案，枚举链尾的前一个数
d
d
d，注意环个数的变化所带来的正负号影响。
我们只需要求出
∑
i
=
1
n
f
n
\sum_{i=1}^n f_n
∑i=1n?fn? 即可，发现这也是可以用类似杜教筛的方法来做的：
∑
i
=
1
n
f
i
=
∑
i
=
1
n
(
C
(
1
?
C
)
n
?
1
∑
d
∣
i
,
d
≠
i
C
1
?
C
f
d
)
=
n
C
(
1
?
C
)
n
?
1
+
∑
d
=
1
n
f
d
?
C
1
?
C
(
?
n
d
?
?
1
)
\begin{aligned} \sum_{i=1}^nf_i&=\sum_{i=1}^n\left(C(1-C)^{n-1}\sum_{d|i,d\neq i}\frac{C}{1-C}f_d\right)\\ &=nC(1-C)^{n-1}+\sum_{d=1}^nf_d\cdot\frac{C}{1-C}\left(\left\lfloor\frac{n}{d}\right\rfloor-1\right) \end{aligned}
i=1∑n?fi??=i=1∑n????C(1?C)n?1d∣i,d?=i∑?1?CC?fd????=nC(1?C)n?1+d=1∑n?fd??1?CC?(?dn???1)?
有一个问题是如何线性预处理小范围的
∑
i
=
1
n
f
i
\sum_{i=1}^n f_i
∑i=1n?fi?。发现
f
i
f_i
fi? 只与
i
i
i 的因子的形态有关：具体来说，设
i
=
p
1
a
1
?
p
k
a
k
i=p_1^{a_1}\cdots p_k^{a_k}
i=p1a1???pkak??，那么
f
i
f_i
fi? 只与可重集
{
a
i
}
\{a_i\}
{ai?} 有关。
那么我们为每种
{
a
i
}
\{a_i\}
{ai?} 选一个符合它的最小的数作为代表元（具体来说，将
a
i
a_i
ai? 从大到小排序后，取代表元为
2
a
1
3
a
2
?
2^{a_1}3^{a_2}\cdots
2a1?3a2??），并只对这些代表元暴力求。
代表元数量很小（实测小于等于
2
×
1
0
7
2\times 10^7
2×107 的代表元只有不到
600
600
600 个，所以对它们每个都根号暴力求都没问题），这样就能做到线性预处理
O
(
n
2
3
)
O(n^{\frac{2}{3}})
O(n32?) 内的前缀和了。
时间复杂度
O
(
n
2
3
)
O(n^{\frac{2}{3}})
O(n32?)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
namespace modular
{
const int mod=998244353;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
inline void Add(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
inline void Dec(int &x,int y){x=x-y<0?x-y+mod:x-y;}
inline void Mul(int &x,int y){x=1ll*x*y%mod;}
}using namespace modular;
inline int poww(int a,ll b)
{
int ans=1;
while(b)
{
if(b&1) ans=mul(ans,a);
a=mul(a,a);
b>>=1;
}
return ans;
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
const int n2=300000,n3=20000000;
const int N2=n2+10,N3=n3+10;
ll n;
int C,K,coef;
int idx,id1[N2],id2[N2];
int cnt,prime[N3],mup[N3],omega[N3],sign[N3];
bool notprime[N3];
int sumf[N2],pref[N3],ff[N3];
int &id(ll x){return x<=n2?id1[x]:id2[n/x];}
void init()
{
mup[1]=1,omega[1]=0;
for(int i=2;i<=n3;i++)
{
if(!notprime[i])
{
prime[++cnt]=i;
mup[i]=i,omega[i]=1;
}
for(int j=1,v;j<=cnt&&(v=i*prime[j])<=n3;j++)
{
notprime[v]=1;
if(!(i%prime[j]))
{
mup[v]=mup[i],omega[v]=omega[i];
break;
}
mup[v]=mup[i]*prime[j],omega[v]=omega[i]+1;
}
}
vector<int> sp;
sp.push_back(1);
for(int i=1;i<=cnt;i++)
{
sp.push_back(sp.back()*prime[i]);
if(sp.back()>n3) break;
}
sign[1]=1,ff[1]=K;
for(int i=2;i<=n3;i++)
{
sign[i]=sign[i/mup[i]]*sp[omega[i]];
if(i!=sign[i])
{
ff[i]=ff[sign[i]];
continue;
}
ff[i]=K;
for(int j=1;j*j<=i;j++)
{
if(!(i%j))
{
Add(ff[i],mul(coef,ff[j]));
if(j>1&&j*j!=i) Add(ff[i],mul(coef,ff[i/j]));
}
}
}
for(int i=1;i<=n3;i++) pref[i]=add(pref[i-1],ff[i]);
}
int solve(ll n)
{
if(n<=n3) return pref[n];
if(sumf[id(n)]!=-1) return sumf[id(n)];
int ans=mul(n%mod,K);
for(ll l=1,r;;l=r+1)
{
r=n/(n/l);
if(r==n) break;
Add(ans,mul(mul(coef,(n/l-1)%mod),dec(solve(r),solve(l-1))));
}
return sumf[id(n)]=ans;
}
int main()
{
cin>>n>>C;
if(C==1)
{
puts(n<=2?"1":"0");
return 0;
}
K=mul(C,poww(dec(1,C),n-1));
coef=mul(C,poww(dec(1,C),mod-2));
for(ll l=1,r;l<=n;l=r+1)
r=n/(n/l),id(n/l)=++idx;
init();
memset(sumf,-1,sizeof(sumf));
int res=solve(n);
printf("%d\n",add(poww(dec(1,C),n),res));
return 0;
}
|