记录编号	413329	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]香蕉	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.714 s
提交时间	2017-06-11 13:15:23	内存使用	2.61 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
const int N=1e5+10,SIZE=161,p=119<<23|1;
typedef unsigned long long ull;
map<vector<int>,int> M;
vector<int> cnt[N];
int n,m,mi[N],size,id[N];
struct matrix{
	int a[SIZE][SIZE];
	matrix(){memset(a,0,sizeof a);}
	void operator *= (const matrix &x){
		static int ans[SIZE][SIZE];
		for (int i=0;i<size;i++)
		for (int j=0;j<size;j++){
			ull sum=0;int cnt=0;
			for (int k=0;k<size;k++){
				sum+=(ull)a[i][k]*x.a[k][j];
				cnt++;
				if (cnt==10) cnt=0,sum%=p;
			}
			ans[i][j]=sum%p;
		}
		memcpy(a,ans,sizeof a);
	}
}x,ans;
bool vis[N];int num[SIZE];
void init(){
	for (int i=2;i<=m;i++)
	if (cnt[i].empty()){
		for (int j=i;j<=m;j+=i) cnt[j].push_back(mi[j]=mi[j/i]+1);
		for (int j=i;j<=m;j+=i) mi[j]=0;
	}
	for (int i=1;i<=m;i++){
		sort(cnt[i].begin(),cnt[i].end());
		id[i]=M[cnt[i]];
		if (!id[i]) id[i]=M[cnt[i]]=size++,vis[i]=1;
		num[id[i]]++;
	}
	for (int i=0;i<size;i++)
	for (int j=0;j<size;j++)
		x.a[i][j]=num[j];
	for (int i=1;i<=m;i++)
	for (int j=i+i;j<=m;j+=i)
		if (vis[j]) x.a[id[j]][id[i]]--;
	/*for (int i=0;i<size;i++,puts(""))
	for (int j=0;j<size;j++) printf("%d ",x.a[i][j]);
	printf("%d\n",size);*/
}
int main()
{
	freopen("Banana.in","r",stdin);
	freopen("Banana.out","w",stdout);
	scanf("%d%d",&n,&m);
	init();
	for (int i=0;i<size;i++) ans.a[0][i]=num[i];
	for (n--;n;n>>=1,x*=x)
		if (n&1) ans*=x;
	ull Ans=0;
	for (int i=0;i<size;i++) Ans+=ans.a[0][i];
	printf("%d\n",int(Ans%p));
	return 0;
}