思路

$\dbinom{N}{K}=\dfrac{\prod_{i=N-K+1}^Ni}{ \prod_{i=1}^Ki}$。

考虑因式分解定理，$x=p_1^{q_1}p_2^{q_2}p_3^{q_3}\dots$，则 $x$ 的因子有 $\prod (q_i+1)$ 个。

我们现在想知道的就是 $\dfrac{\prod_{i=N-K+1}^Ni}{ \prod_{i=1}^Ki}$ 的每个质因数出现的次数。考虑两段长度均为 $K$，每一段中大于 $K$ 的因数在其中最多出现一次。那么我们可以对上面和下面分别进行区间筛（$1\sim 10^6$），然后对于所有筛完不是 $1$ 的数肯定是素数（$\sqrt{N}\leq$ 的因数最多只有一种一个）。所以总复杂度是 $\Theta(10^6\ln 10^6)$，可以通过。

代码

#include <bits/stdc++.h>
#define int long long
#define double long double
#define mid ((l+r)>>1)
using namespace std;
const int mod=998244353;
bool isp[1000005];
int now[1000005];
int cnt[1000005];
signed main(){
	//freopen("","r",stdin);
	//freopen("","w",stdout);
	int n,k;
	cin>>n>>k;
	for(int i=2;i<=1000000;i++) isp[i]=1;
	for(int i=2;i<=1000000;i++) if(isp[i]) for(int j=i*2;j<=1000000;j+=i) isp[j]=0;
	for(int i=1;i<=k;i++) now[i]=i;
	for(int i=2;i<=1000000;i++){
		int fst=i;
		for(int j=fst;j<=k;j+=i){
			while(now[j]%i==0){
				now[j]/=i;
				cnt[i]--;
			}
		}
	}
	for(int i=1;i<=k;i++) now[i]=n-k+i;
	for(int i=2;i<=1000000;i++){
		int fst=((n-k)/i+1)*i;
		for(int j=fst;j<=n;j+=i){
			while(now[j+k-n]%i==0){
				now[j+k-n]/=i;
				cnt[i]++;
			}
		}
	}
	int ans=1;
	for(int i=2;i<=1000000;i++){
		ans=ans*(cnt[i]+1)%mod;
	}
	for(int i=1;i<=k;i++) if(now[i]!=1) ans=ans*2%mod;
	cout<<ans;
}