Loading [MathJax]/extensions/TeX/mathchoice.js

【NOI2017】泳池 排行榜


时间限制: 3 s
空间限制: 524288 KB

题目描述

久莲是个爱玩的女孩子。

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

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

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

例如:当 N=5 时,若测量的结果如下(因为 1001 太大,这儿只画出网格最下面三行的信息,其他部分都是危险的)。

游泳池

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

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

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

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

输入格式

从标准输入读入数据。

输入一行四个正整数 N,K,x,y,其中 1x<y<998244353q 的取值为 xy

输出格式

输出到标准输出。

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

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

样例输入

样例输出

提示

x^{p-1} \equiv 1 \mod p,其中 p 为质数,x \in [1,p)

数据范围

测试点编号NK
1,2=1\leq 1000
3\leq 10\leq 8
4\leq 10\leq 9
5\leq 10\leq 10
6\leq 1000\leq 7
7\leq 1000\leq 8
8\leq 1000\leq 9
9,10,11\leq 1000\leq 100
12,13,14\leq 1000\leq 1000
15,16\leq 10^9\leq 10
17,18\leq 10^9\leq 100
19,20\leq 10^9\leq 1000

题目来源

NOI 2017 Day 1


关于接口中的数组初值说明(最后更新:2023年2月6日)

若题目要求实现函数接口,且该函数中存在仅用于输出的数组(如 void solve(int n, const int *in, int *out) 中的 out),那么除非另外说明,否则该数组在程序启动时的初值为 0

关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。

关于提交的说明

你提交的代码将会被公开,所有人都可见。如果这不是你所期望的,或者如果想要删除已提交的代码,请联系管理员。




Judge Duck Online | 评测鸭在线
Server Time: 2025-08-25 23:42:41 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠