本题是否有存在方案数大于998244353的数据？

正文

在题目中，我用了没有加取模操作的代码通过了本题，代码如下，我惊奇的发现本题竟然可以在不加取模操作的情况下通过，这让我不禁思考是否存在

n\le 1e12

的数据使得方案数大于题目中所给出的模数，在询问AI后，AI给出的答复是不存在，而在代码的实测上我将取模后了的正确代码跑了很久都没出现一组数据有方案数大于题目所给的

998244353

，所以请问是否有解，题目中的取模是不是多余了？

代码（没有加取模操作）

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,p=998244353,ys[1000000],dp[7000][7000];//dp[i][j]->当前是i且乘积里面的最大值是j的个数
map<int,int>mp;
void chuli() {
	cin>>n;
	ys[0]=0;
	for(int i=1; i<=sqrt(n); i++)if(n%i==0)ys[++ys[0]]=i,ys[ys[0]+=(i!=(n/i))]=n/i;
	sort(ys+1,ys+1+ys[0]);
	for(int i=1;i<=ys[0];i++)mp[ys[i]]=i;
	for(int i=1;i<=ys[0];i++)for(int j=1;j<=ys[0];j++)dp[i][j]=0;
	for(int i=1; i<=ys[0]; i++) {
		dp[i][i]=1;
		for(int j=1; j<i; j++){
			dp[i][j]+=dp[i][j-1];
			if(ys[i]%ys[j]==0)dp[i][j]+=dp[mp[ys[i]/ys[j]]][j-1];
		}
		for(int j=i;j<=ys[0];j++)dp[i][j]+=dp[i][j-1];
	}
	cout<<dp[ys[0]][ys[0]]-1<<'\n';
	return ;
}
signed main() {
	cin>>T;
	while(T--)chuli();
	return 0;
}

本题是否有存在方案数大于998244353的数据？

讨论操作

正文

代码（没有加取模操作）

回复

相关推荐

本题是否有存在方案数大于998244353的数据？