machine 一道数论题目。
题目
题目描述
一句话题意:给定 \(f _ 0(n)\),有 \(m\) 组询问,每组询问给定 \(k,x\),求 \((f _ 0\ast 1^k)(x)\pmod{998244353}\)。
想看详细题意可以看原题 pdf。
数据范围
对于 \(10\%\) 的数据,\(m=0\);
对于 \(20\%\) 的数据,\(m\leq 5\);
对于另 \(30\%\) 的数据,\(f _ 0[i]\) 全都是 \(1\);
对于另 \(30\%\) 的数据,所有询问的 \(k\) 相等;
对于 \(100\%\) 的数据,\(n\leq 10^5,m\leq 1000,0\leq f _ 0[i]<998244353,k\leq 10^5,x\leq n\)。
时空限制
- machine.cpp/in/out
- Time limit: 4s
- Memory limit: 512MB
题解
解法 A(人口普查)
对于 \(10\%\) 的数据,\(m=0\)。
我们直接提交一个可以通过编译的空白主函数程序即可。
解法 B(小发现)
对于 \(20\%\) 的数据,\(m\leq 5\)。
我们不妨考虑直接模拟 \(\texttt{Dirichlet}\) 卷积的过程,并且加一点点的小优化(询问按 \(k\) 排序),时间复杂度为 \(\Theta(mn\ln n\max\{k\})\),显然过不掉。
考虑 \(\texttt{Dirichlet}\) 卷积的式子。
\[f _ k(n)=\sum _ {d\mid n}f _ {k-1}(d)\]
我们不难发现,\(\texttt{Dirichlet}\) 卷积既符合交换律又符合结合律。
所以我们可以通过快速幂的方式优化卷积过程,时间复杂度为 \(\Theta(mn\ln n\log _ 2\max\{k\})\)。
解法 C(小推广)
对于另 \(30\%\) 的数据,所有询问的 \(k\) 相等。
与解法 B 相同的,我们用快速幂优化卷积过程,最后的时间复杂度为 \(\Theta(n\ln n\log _ 2k+m)\)。
解法 D(臃肿的写法)
这是 std 的解法。
对于一个数 \(n\),我们不难分解它为
\[n=\prod _ {p _ i\in\mathbb{P} _ n}p _ i^{c _ i}\]
对于一个数 \(n\),我们根据分解的结果定义一个数列
\[c _ 1,c _ 2,\cdots,c _ t\]
其中有
\[c _ 1\leq c _ 2\leq c _ 3\leq\cdots\leq c _ t\]
我们规定,如果两个数对应的数列相同,我们就称这两个数是乘法同构的。
不难观察到(打表即可),对于小于等于 \(10^5\)(本题 \(n\) 的范围)的数中,根据乘法同构分类,本质不同的数仅有 \(160\) 个(题解里面写的是 \(165\) 个,显然是不认真思考,抄别人代码写的题解)。
于是我们考虑用乘法同构矩阵优化 \(\texttt{Dirichlet}\) 卷积过程。
最后的时间复杂度为
\[\Theta(n\log^2 _ 2n+n\ln n+|S|^3\log _ 2k+m(|S|^2\log _ 2k+\sqrt{x}))\]
奇慢无比。
代码
std 的做法太慢了,代码还长。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define MOD 998244353 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } inline int add(reg int a,reg int b){ reg int sum=a+b; return sum>=MOD?sum-MOD:sum; } const int MAXN=100000+5; const int MAXLOG2K=17+1; int n,m; int f[MAXN]; int col[MAXN]; int link[MAXN]; map<vector<int>,int> S; bool vis[MAXN]; int tot,prime[MAXN]; int from[MAXN]; inline void Init(reg int n){ vis[1]=true; from[1]=1; for(reg int i=2;i<=n;++i){ if(!vis[i]){ prime[++tot]=i; from[i]=i; } for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){ vis[i*prime[j]]=true; from[i*prime[j]]=prime[j]; if(i%prime[j]==0) break; } } return; } const int MAXCNT=160+1+5; struct Matrix{ int n,m; int unit[MAXCNT][MAXCNT]; inline Matrix(void){ n=m=0; memset(unit,0,sizeof(unit)); return; } inline int* operator[](reg int i){ return unit[i]; } inline Matrix operator*(const Matrix &a)const{ Matrix res; res.n=n,res.m=a.m; reg int r; for(reg int i=1;i<=n;++i) for(reg int k=1;k<=m;++k){ r=unit[i][k]; for(reg int j=1;j<=a.m;++j) res[i][j]=add(res[i][j],1ll*r*a.unit[k][j]%MOD); } return res; } }; Matrix base[MAXLOG2K]; int main(void){ //freopen("machine.in","r",stdin); //freopen("machine.out","w",stdout); n=read(); for(reg int i=1;i<=n;++i) f[i]=read(); Init(1e5); reg int cnt=0; col[++cnt]=1; link[1]=1; for(reg int i=2;i<=n;++i){ vector<int> V; reg int tmp=i; while(tmp!=1){ reg int p=from[tmp]; int cnt=0; while(tmp%p==0) tmp/=p,++cnt; V.push_back(cnt); } sort(V.begin(),V.end()); if(S.count(V)) col[i]=S[V]; else{ col[i]=S[V]=++cnt; link[i]=1; } } base[0].n=base[0].m=cnt; for(reg int i=1;i<=n;++i) for(reg int k=1;i*k<=n;++k) base[0][col[i]][col[i*k]]+=link[i*k]; for(reg int i=1;i<MAXLOG2K;++i) base[i]=base[i-1]*base[i-1]; m=read(); while(m--){ static int k,x; k=read(),x=read(); Matrix A; A.n=1,A.m=cnt; A[1][1]=1; for(reg int i=0;i<MAXLOG2K;++i) if((k>>i)&1) A=A*base[i]; reg int ans=0; for(reg int i=1;i*i<=x;++i) if(x%i==0){ ans=add(ans,1ll*A[1][col[x/i]]*f[i]%MOD); if(i*i!=x) ans=add(ans,1ll*A[1][col[i]]*f[x/i]%MOD); } printf("%d\n",ans); } return 0; }
解法 E(人类智慧)
考虑递推式
\[
\begin{aligned}
f _ k(n)&=\sum _ {d _ 1\mid n}f _ {k-1}(d _ 1)\\
&=\sum _ {d _ 1\mid n}\sum _ {d _ 2\mid d _ 1}f _ {k-2}(d _ 2)\\
&=\sum _ {d _ 1\mid n}\sum _ {d _ 2\mid d _ 1}\sum _ {d _ 3\mid d _ 2}f _ {k-3}(d _ 3)\\
&=\sum _ {d _ 1\mid n}\sum _ {d _ 2\mid d _ 1} \cdots \sum _ {d _ {i+1}\mid d _ i}\cdots\sum _ {d _ k\mid d _ {k-1}}f _ 0(d _ k)
\end{aligned}
\]
我们不妨变换一下形式
\[
\begin{aligned}
f _ k(n)&=\sum _ {d _ 1\mid n}\sum _ {d _ 2\mid d _ 1} \cdots \sum _ {d _ {i+1}\mid d _ i}\cdots\sum _ {d _ k\mid d _ {k-1}}f _ 0(d _ k)\\
&=\sum _ {d _ k\mid d _ {k-1}}f _ 0(d _ k)[d _ k\mid d _ {k-1}\mid\cdots\mid d _ 2\mid d _ 1\mid n]\\
&=\sum _ {d _ k\mid n}f _ 0(d _ k)[d _ k\mid d _ {k-1}\mid\cdots\mid d _ 2\mid d _ 1\mid n]
\end{aligned}
\]
此时我们注意到后面的特征函数
\[
[d _ k\mid d _ {k-1}\mid\cdots\mid d _ 2\mid d _ 1\mid n]
\]
我们把上面的 \(d\) 看作分解后得到的集合,则
\[
\mathbb{P} _ {d _ k}\subseteq\mathbb{P} _ {d _ {k-1}}\subseteq\mathbb{P} _ {d _ {k-2}}\subseteq\cdots\subseteq\mathbb{P} _ {d _ 2}\subseteq\mathbb{P} _ {d _ 1}\subseteq\mathbb{P} _ n
\]
不难发现,我们本质上就是要求满足上述子集链关系的方案数,方案数与 \(f _ 0(d _ k)\) 的乘积即为对答案的贡献。
我们考虑把所有集合都消去一个 \(\mathbb{P} _ {d _ k}\),这对答案没有影响,然后得到
\[
\begin{matrix}
\mathbb{P} _ {d _ k}&\subseteq&\mathbb{P} _ {d _ {k-1}}&\subseteq&\cdots&\subseteq&\mathbb{P} _ {d _ 1}&\subseteq&\mathbb{P} _ n\\
\downarrow&&\downarrow&&\downarrow&&\downarrow&&\downarrow\\
\varnothing&\subseteq&\mathbb{S} _ 1&\subseteq&\cdots&\subseteq&\mathbb{S} _ {k-1}&\subseteq&(\mathbb{P} _ n-\mathbb{P} _ {d _ k})
\end{matrix}
\]
\[
\varnothing\subseteq\mathbb{S} _ 1\subseteq\mathbb{S} _ 2\subseteq\cdots\subseteq\mathbb{S} _ {k-2}\subseteq\mathbb{S} _ {k-1}\subseteq(\mathbb{P} _ n-\mathbb{P} _ {d _ k})
\]
考虑子集符号象征着集合之间的差(变化),我们可以分开质因子讨论。
上述链中共有 \(k\) 个子集符号。
对于一个质因子 \(p _ i\),它在 \((\mathbb{P} _ n-\mathbb{P} _ {d _ k})\) 中的出现次数为 \(c _ i\),那么它单独的方案数目可以转化为:
\(c _ i\) 个相同小球放入 \(k\) 个不同盒子中,允许有的盒子空着的方案数。
用插板法可以求得为 \(\binom{k+c _ i-1}{k-1}=\binom{k+c _ i-1}{c _ i}\)。
再用乘法原理对质因子对方案数的贡献进行合并,直接乘起来即可。
最后得出答案的表达式
\[
f _ k(x)=\sum _ {d\mid x}f _ 0(d)\prod _ {c _ i\in(\mathbb{P} _ x-\mathbb{P} _ d)}\binom{k+c _ i-1}{c _ i}\pmod{998244353}
\]
这种做法快到飞起,时间复杂度为 \(\Theta(n+m\sum _ {d\mid x}\sqrt{d})\),其中 \(\Theta(n)\) 的复杂度用于预处理阶乘及其逆元,实际上的复杂度跑不满,实际测试趋近于 \(\Theta(n+m\log _ 2m)\)。
代码
时间效率是解法 D 的 200 倍(平均一个点 0.01s),并且代码还短了一半。
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; #define MOD 998244353 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return res; } const int MAXN=100000+5; const int MAXS=500000+5; inline int add(reg int a,reg int b){ reg int sum=a+b; return sum>=MOD?sum-MOD:sum; } int n; int f[MAXN]; int fac[MAXS],invfac[MAXS]; inline int pow(reg int x,reg int exp){ reg int res=1; while(exp){ if(exp&1) res=1ll*res*x%MOD; x=1ll*x*x%MOD; exp>>=1; } return res; } inline void Init(reg int n){ fac[1]=invfac[1]=1; for(reg int i=2;i<=n;++i) fac[i]=1ll*fac[i-1]*i%MOD; invfac[n]=pow(fac[n],MOD-2); for(reg int i=n-1;i>=2;--i) invfac[i]=1ll*invfac[i+1]*(i+1ll)%MOD; return; } inline int C(reg int n,reg int m){ return 1ll*fac[n]*invfac[m]%MOD*invfac[n-m]%MOD; } inline int Solve(reg int x,reg int k){ reg int res=1; for(reg int i=2;i*i<=x;++i) if(x%i==0){ reg int cnt=0; while(x%i==0) ++cnt,x/=i; res=1ll*res*C(k+cnt-1,cnt)%MOD; } if(x>1) res=1ll*res*k%MOD; return res; } int main(void){ Init(5e5); n=read(); for(reg int i=1;i<=n;++i) f[i]=read(); reg int m=read(); while(m--){ static int k,x; k=read(),x=read(); reg int ans=0; for(reg int i=1;i*i<=x;++i) if(x%i==0){ ans=add(ans,1ll*f[i]*Solve(x/i,k)%MOD); if(i*i!=x) ans=add(ans,1ll*f[x/i]*Solve(i,k)%MOD); } printf("%d\n",ans); } return 0; }
近期评论