{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch3\u003e题目背景\u003c/h3\u003e\n\u003cp\u003e\u003cimg src\u003d\"CDN_BASE_URL/d3fb881402f40d90c1602ed07c63f6eb?v\u003d1725679193\" alt\u003d\"\"\u003e\u003c/p\u003e\n\u003ch3\u003e题目描述\u003c/h3\u003e\n\u003cp\u003eAPJifengc 想要练习它的动态视力,所以他开始练习打 \u003ca href\u003d\"https://www.bilibili.com/video/BV1H14y1n7sB/?t\u003d190\" target\u003d\"_blank\"\u003eLimbo 的结尾段\u003c/a\u003e。\u003c/p\u003e\n\u003cp\u003e这一段的规则是这样的:有 $n$ 个钥匙形成一个环,这 $n$ 个钥匙中有 $1$ 个是真钥匙,剩下的 $n-1$ 个均为假钥匙。这些钥匙会进行 $m$ 次打乱,打乱的过程是每次等概率随机一个长度为 $n$ 的排列 $\\{p_i\\}$,然后将第 $i$ 个钥匙移动到 $p_i$ 的位置。打乱完 $m$ 次后,APJifengc 需要选出正确的钥匙。如果选择错误,那么 APJifengc 就需要重新开始。\u003c/p\u003e\n\u003cp\u003e但是,APJifengc 的动态视力并没有训练到能够 $100\\%$ 看清每次打乱的地步。具体来说,每进行一次打乱,APJifengc 有 $\\frac{1}{p}$ 的概率看不清钥匙是怎么打乱的。那么,此时 APJifengc 有两种选择,一种是直接重开,另一种是等到 $m$ 次打乱结束后,凭运气猜一个钥匙,如果最后没有猜中,那么只能重开。\u003c/p\u003e\n\u003cp\u003e我们规定钥匙每旋转一轮就会经过 $1$ 的单位时间,重开与最后的选择钥匙不消耗时间。APJifengc 想要知道,期望经过多少单位时间后,他能够选中正确的钥匙。\u003c/p\u003e\n\u003cp\u003e由于 APJifengc 是个很精细的人,他想要知道极其精确的答案,但他同时也需要一个粗略的估计,所以你需要\u003cstrong\u003e同时输出答案的实数值与模 $998244353$ 意义下的值\u003c/strong\u003e。关于期望值在模 $998244353$ 意义下的定义,请见题目最后面的补充。\u003c/p\u003e\n\u003cp\u003e当然,如果你求不出精确值,APJifengc 也不会为难你,如果你只答对了实数值,那么你将获得本题 $60\\%$ 的分数。\u003c/p\u003e\n\u003ch3\u003e输入格式\u003c/h3\u003e\n\u003cp\u003e输入包括一行四个整数 $t, n, m, p$。其中 $t \u003d 0$ 表示只需要输出实数值,$t \u003d 1$ 表示除了实数值以外,还需要输出精确值。$n, m, p$ 的含义见题目描述。\u003c/p\u003e\n\u003ch3\u003e输出格式\u003c/h3\u003e\n\u003cp\u003e对于 $t \u003d 0$,输出包括一行,为一个实数。如果你的答案与正确答案的绝对或相对误差不超过 $10^{-6}$,即判定为正确。\u003c/p\u003e\n\u003cp\u003e对于 $t \u003d 1$,额外输出一行,为一个整数,表示期望时间在模 $998244353$ 意义下的答案。\u003c/p\u003e\n\u003ch3\u003e数据范围\u003c/h3\u003e\n\u003ctable\u003e\n\u003cthead\u003e\n\u003ctr\u003e\n\u003cth\u003e测试点编号\u003c/th\u003e\n\u003cth\u003e$n, m \\le$\u003c/th\u003e\n\u003cth\u003e特殊性质\u003c/th\u003e\n\u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n\u003ctr\u003e\n\u003ctd\u003e1,2,3\u003c/td\u003e\n\u003ctd\u003e$10$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 0$\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e4,5\u003c/td\u003e\n\u003ctd\u003e$10$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 1$\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e6,7,8,9,10,11,12,13,14\u003c/td\u003e\n\u003ctd\u003e$10^2$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 0$\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e15,16,17,18,19,20\u003c/td\u003e\n\u003ctd\u003e$10^2$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 1$\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e21,22,23\u003c/td\u003e\n\u003ctd\u003e$10^5$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 0$\u003c/td\u003e\n\u003c/tr\u003e\n\u003ctr\u003e\n\u003ctd\u003e24,25\u003c/td\u003e\n\u003ctd\u003e$10^5$\u003c/td\u003e\n\u003ctd\u003e$t \u003d 1$\u003c/td\u003e\n\u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e对于所有的数据,满足 $1 \\le n, m \\le 10^5, 2 \\le p \\le 5 \\times 10^5$。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e在合理的范围内,选手无需担心浮点数误差带来的精度问题。\u003c/strong\u003e\u003c/p\u003e\n\u003ch3\u003e补充\u003c/h3\u003e\n\u003cp\u003e\u003cstrong\u003e期望值在模意义下的定义:\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e假设答案期望值为 $\\frac{a}{b}$,那么你需要输出一个整数 $x$,满足 $x b \\equiv a \\pmod {998244353}$。\u003c/p\u003e\n"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e0 2 2 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e\u003cp\u003e此时的最优策略为如果没有看清,就直接等最后猜钥匙。\u003c/p\u003e\n\u003cul\u003e\n\u003cli\u003e有 $\\frac{1}{4}$ 的概率可以准确知道真钥匙的位置;\u003c/li\u003e\n\u003cli\u003e有 $\\frac{3}{4}$ 的概率不能准确知道真钥匙的位置;\n\u003cul\u003e\n\u003cli\u003e其中,有 $\\frac{1}{2}$ 的概率能够猜中,$\\frac{1}{2}$ 的概率不能猜中。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003e综上,经过一轮后能够选中真钥匙的概率为 $\\frac{1}{4} + \\frac{3}{4} \\times \\frac{1}{2} \u003d \\frac{5}{8}$,不能选中真钥匙的概率为 $\\frac{3}{4} \\times \\frac{1}{2} \u003d \\frac{3}{8}$。那么期望时间为 $2 + \\frac{3}{8}\\left(2 + \\frac{3}{8}\\left(2 + \\cdots\\right)\\right) \u003d \\frac{16}{5}$。\u003c/p\u003e\n\u003cp\u003e虽然在本样例中 $t \u003d 0$,对于精确值没有要求,这里给出其精确值在模意义下的值,为 $598946615$。\u003c/p\u003e\n"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 4 6 15\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7.491314735096\n315581326\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 82 97 114\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e153.933361371106\n422268238\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}