前言

没有前言。

思路

考虑 dp，带点推公式。

首先，众所周知，计算正因数个数是有公式的：设 $x=\prod p_{i}^{c_{i}}$，其中 $p_{i}$ 都为质数，$c_{i}$ 都为非负整数，那么 $x$ 的正因数个数为 $\prod (c_{i}+1)$。

接着，假设在原来正因数个数为 $\prod (c_{i}+1)$ 的基础上乘上一个数 $x$，设 $g_{x,i}$ 表示 $x$ 最多能整除多少个 $p_{i}$，正因数个数就会变成 $\prod (c_{i}+g_{x,i}+1)$，但是，在 dp 的过程中不可能记录下来所有 $c_{i}$ 的值，只能记录整体的乘积，所以我们需要把公式中的 $g_{x,i}$ 拆出来，这么一来，设可能拥有的质因数集合为 $S$，那么：

$$\prod (c_{i}+g_{x,i}+1)=\sum_{T \subset S}\left(\prod_{i \in T}(c_{i}+1)\right)\left(\prod_{i \in S,i \notin T} g_{x,i}\right)$$

这样，我们就只需要记录对于所有的 $T$ 的 $\prod_{i \in T}(c_{i}+1)$ 就好了。

那么，dp 状态就出来了：$f_{i,S}$ 代表长度为 $i$ 的，只计算集合 $S$ 内的质因数的贡献值之和。

dp 转移即为：

$$f_{i,S}=\sum_{T \subset S} f_{i-1,T} \sum_{j=1}^{m}\prod_{k \in S,k \notin T} g_{j,k}$$

但是，朴素的 dp 时间复杂度为 $O(n \times m \times \pi(m) \times 3^{\pi(m)})$，而 $n$ 的值域极大，所以不能通过。

想到矩阵乘法优化 dp：设 $F_{i}$ 为矩阵 $[\begin{matrix} f_{i,0}&f_{i,1} & ... &\end{matrix}]$——所有 $f_{i,S}$ 依次排列的矩阵，考虑如何构造出矩阵 $R$，使得 $F_{i}=F_{i-1} \times R$。先展开矩阵乘的式：

$$F_{i,k}=\sum_{j} F_{i-1,j} \times R_{j,k}$$

然后对比上方 dp 转移式，发现对于集合 $S$：

$$\forall T \subset S,R_{T,S}=\sum_{j=1}^{m}\prod_{k \in S,k \notin T} g_{j,k} \\ \forall T \not\subset S,R_{T,S}=0$$

然后你发现还没做完——它要求所有 dp 值的和吧！？

其实我们可以在矩阵 $F_{i}$ 的最后一位弄一个表示前对于所有的 $j \le i$ 和任意 $S$，$f_{j,S}$ 的和，设这一位为 $P$，那么：

$$\begin{aligned} F_{i,P}&=F_{i-1,P}+\sum_{S} F_{i,S} \\ &=F_{i-1,P}+\sum_{S} \sum_{T} F_{i-1,T} \times R_{T,S} \end{aligned}$$

而，展开矩阵式，又有：

$$F_{i,P}=\sum_{j} F_{i-1,j} \times R_{j,P}$$

对比上方式子，可以推出：

$$R_{T,P}=\sum_{S \supset T} R_{T,S} \\ R_{P,P}=1$$

所以，$R$ 矩阵总算构造完成啦！

对矩阵 $R$ 做矩阵快速幂就做完啦！

预处理时间复杂度：$O(m \times \pi(m) \times 3^{\pi(m)})$。

矩阵快速幂时间复杂度：$O(\log n \times (2^{\pi(m)}+1)^3)$。

可以通过本题。

代码

#include<stdio.h>
#include<string.h>
#define ll long long
const int M=17,K=6,MO=998244353;
int m,ans,pri[]={2,3,5,7,11,13},g[M][K];
ll n;
struct Matrix{
	int a[(1<<K)+1][(1<<K)+1];
	Matrix(){memset(a,0,sizeof(a));}
	Matrix operator*(const Matrix &o)const{
		Matrix t;
		for(int i=0;i<=(1<<K);i++){
			for(int j=0;j<=(1<<K);j++){
				for(int k=0;k<=(1<<K);k++){
					t.a[i][k]+=1ll*a[i][j]*o.a[j][k]%MO,t.a[i][k]%=MO;
				}
			}
		}
		return t;
	}
};
Matrix R;
void get_g(){
	for(int i=1;i<=m;i++){
		int x=i;
		for(int j=0;j<6;j++){
			while(x%pri[j]==0) g[i][j]++,x/=pri[j]; 
		}
	}
}
void get_R(){
	for(int S=0;S<(1<<K);S++){
		for(int T=S;;T=(T-1)&S){
			for(int j=1;j<=m;j++){
				int p=1;
				for(int k=0;k<6;k++){
					if((S&(1<<k))&&!(T&(1<<k))) p=1ll*p*g[j][k]%MO;
				}
				R.a[T][S]+=p,R.a[T][S]%=MO;
			}
			R.a[T][1<<K]+=R.a[T][S];
			if(!T) break;
		}
	}
	R.a[1<<K][1<<K]=1;
}
Matrix fp(Matrix x,ll y){
	Matrix t=x;
	y--;
	while(y){
		if(y&1) t=t*x;
		x=x*x,y>>=1;
	}
	return t;
}
int main(){
	scanf("%lld%d",&n,&m);
	get_g();
	get_R();
	R=fp(R,n);
	printf("%d\n",R.a[0][1<<K]);
	return 0;
}