「UOJ316」[Noi2017]泳池

Description

久莲是个爱玩的女孩子。

暑假终于到了,久莲决定请她的朋友们来游泳,她打算先在她家的私人海滩外圈一块长方形的海域作为游泳场。然而大海里有着各种各样的危险,有些地方水太深,有些地方有带毒的水母出没。她想让圈出来的这一块海域都是安全的。

经过初步分析,这块海域可视为一个底边长为 NN 米,高为 10011001 米的长方形网格。其中网格的底边对应着她家的私人海滩,每一个 1m×1m1\:\textrm{m}\times1\:\textrm{m} 的小正方形都代表着一个单位海域。她拜托了她爸爸明天去测量每一个小正方形是否安全。在得知了信息之后,她要做的就是圈出她想要的游泳场啦。

她心目中理想的游泳场满足如下三个条件:

  • 必须保证安全性。即游泳场中的每一个单位海域都是安全的。
  • 必须是矩形。即游泳场必须是整个网格中的一个 a×ba\times b 的子网格。
  • 必须和海滩相邻。即游泳场的下边界必须紧贴网格的下边界。
    例如:当 N=5N = 5 时,若测量的结果如下(因为 10011001 太大,这儿只画出网格最下面三行的信息,其他部分都是危险的)。

那么她可以选取最下面一行的 1×41\times4 的子海域,也可以选择第三列的 3×13\times1 的子海域。注意她不能选取最上面一行的 1×51\times5 的子海域,因为它没有与海滩相邻。

为了让朋友们玩的开心,她想让游泳场的面积尽可能的大。因此她会选取最下面那一行的 1×41\times4 的子海域作为最终方案。

虽然她要明天才能知道每一个单位海域是否安全,但是她现在就想行动起来估计一下她的游泳场面积有多大。经过简单的估计,她假设每一个单位海域都有独立的 qq 的概率是安全的,1q1 − q 的概率是不安全的。她想要知道她能选择的最大的游泳场的面积__恰好__为 KK 的概率是多少。

然而久莲对数学并不感兴趣,因此她想让你来帮她计算一下这个数值。

Input

输入一行四个正整数 N,K,x,yN,K,x,y,其中 1x<y<9982443531 \leq x < y < 998244353qq 的取值为 xy\frac{x}{y}

Output

输出一行一个整数表示答案在模 998244353998244353 意义下的取值。

即设答案化为最简分式后的形式为 ab\frac{a}{b} ,其中 aabb 的互质。输出整数 xx 使得 bxamod998244353bx \equiv a \mod 9982443530x<9982443530 \leq x < 998244353。可以证明这样的整数 xx 是唯一的。

Sample Input

1
10 5 1 2

Sample Output

1
342025319

HINT

N109,k1000N\leq 10^9,k\leq1000

Solution

fi,jf_{i,j}表示宽度为ii,游泳池高度至少为jj的概率。

fi,j=fi,j+1+k=1ifk1,j×fik,j+1×qj(1q)f_{i,j}=f_{i,j+1}+\sum_{k=1}^if_{k-1,j}\times f_{i-k,j+1}\times q^j(1-q)

因为会算重复,所以钦定右边是fik,j+1f_{i-k,j+1}
满分算法不会呵呵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const ll p = 998244353;
inline ll ksm(ll x, ll y) {
ll res = 1;
for(; y; y >>= 1, x = x * x % p)
if(y & 1) res = res * x % p;
return res;
}
int n, m;
ll x, y, t;
ll f[1100][1100], bin[1100];
//f[i][j] 矩阵宽度占格子为i,最大高度占格子>=j的概率。面积<=s的概率
void add(ll &x, ll v) {
x += v;
if(x >= p) x %= p;
}
ll solve(int s) {
memset(f, 0, sizeof f);
for(int i = 0; i <= 1002; ++i) f[0][i] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 1001; ~ j; --j) {
if(i * j > s) continue;
f[i][j] = f[i][j + 1];
for(int k = 1; k <= i; ++k) {
ll val = f[k - 1][j] * f[i - k][j + 1] % p * bin[j] % p;
add(f[i][j], val);
}
}
}
return f[n][0];
}
int main() {
n = read(), m = read();
x = read(), y = read();
t = x * ksm(y, p - 2) % p;
bin[0] = (1 - t + p) % p;
for(int i = 1; i <= 1002; ++i) bin[i] = bin[i - 1] * t % p;
writeln((solve(m) - solve(m - 1) + p) % p);
return 0;
}