记录编号	411532	评测结果	AAAAAAAAAA
题目名称	[河南省队2016]图计数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.750 s
提交时间	2017-06-05 16:08:20	内存使用	3.34 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=2e5+10,p=999999598,P=p+1;
int n,m,dp[N],size,g[N],f[2][N],*x=f[0],*y=f[1];
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=(ll)x*x%P)
		if (y&1) ans=(ll)ans*x%P;
	return ans;
}
int main()
{
	freopen("graphz.in","r",stdin);
	freopen("graphz.out","w",stdout);
	scanf("%d%d",&n,&m);
	size=sqrt(n);
	x[0]=g[0]=1;
	for (int i=1;i<=size;i++,swap(x,y)){
		for (int j=0;j<=n;j++) y[j]=0;
		for (int j=size+1;j<=n;j++){
			y[j]=inc(y[j-i],x[j-size-1]);
			g[j]=inc(g[j],y[j]);
		}
	}
	dp[0]=1; 
	for (int i=1;i<=size;i++)
	for (int j=i;j<=n;j++)
		dp[j]=inc(dp[j],dp[j-i]);
	int ans=0;
	for (int i=0;i<=n;i++) ans=inc(ans,mul(dp[i],g[n-i]));
	printf("%d\n",power(m,ans));
	return 0;
}