记录编号	440719	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2017]泳池	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	6.549 s
提交时间	2017-08-23 21:10:01	内存使用	15.77 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2010,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?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=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int n,k,x,y,mi[N],dp[N][N];
//dp[i][j]表示笛卡尔树上宽度为i，根深度>=j的合法概率
void multiply(int n,int *a,int *b,int *mod){
	static int ans[N];
	memset(ans,0,sizeof ans);
	for (int i=0;i<=n+1;i++)
	for (int j=0;j<=n+1;j++)
		ans[i+j]=inc(ans[i+j],mul(a[i],b[j]));
	for (int i=n+n+2;i>n;i--){
		int k=ans[i];
		for (int j=0;j<=n+1;j++) ans[i-j]=dec(ans[i-j],mul(k,mod[n+1-j]));
	}
	memcpy(a,ans,sizeof ans);
}
int calc(int S){
	memset(dp,0,sizeof dp);
	for (int i=0;i<=S+1;i++) dp[0][i]=1;
	for (int i=1;i<=S;i++)
	for (int j=S/i;j>=0;j--){
		dp[i][j]=mul(dp[i][j+1],mi[i]);
		for (int k=1;k<=i;k++)//枚举位置在最左边的根
			dp[i][j]=inc(dp[i][j],mul(mul(dp[k-1][j+1],dp[i-k][j]),mul(mi[k-1],dec(1,x))));
	}
	static int mod[N],a[N],f[N],now[N];
	memset(f,0,sizeof f);
	for (int i=0;i<=S;i++) f[i]=dp[i][0];
	memset(mod,0,sizeof mod);
	for (int i=1;i<=S+1;i++) mod[S+1-i]=mul(dp[i-1][1],mul(mi[i-1],dec(x,1)));
	mod[S+1]=1;
	memset(a,0,sizeof a);
	memset(now,0,sizeof now);
	a[0]=1;now[1]=1;
	for (int y=n;y;y>>=1,multiply(S,now,now,mod))
		if (y&1) multiply(S,a,now,mod);
	int ans=0;
	for (int i=0;i<=S;i++) ans=inc(ans,mul(f[i],a[i]));
	return ans;
}
int main()
{
	freopen("pool.in","r",stdin);
	freopen("pool.out","w",stdout);
	scanf("%d%d%d%d",&n,&k,&x,&y);
	x=mul(x,power(y,p-2));
	mi[0]=1;
	for (int i=1;i<N;i++) mi[i]=mul(mi[i-1],x);
	printf("%d\n",dec(calc(k),calc(k-1)));
	return 0;
}