广州网站制作到诺然,百度官网电话,河南最新任免,烘焙食品网站建设需求分析【题目描述】
有一只甲壳虫想要爬上一棵高度为 n 的树#xff0c;它一开始位于树根#xff0c;高度为 0#xff0c;当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根#xff0c;求它从树根爬到树顶时#xff0c;经过的时间的期望值是多少。
【输入格式…【题目描述】
有一只甲壳虫想要爬上一棵高度为 n 的树它一开始位于树根高度为 0当它尝试从高度 i−1 爬到高度为 i 的位置时有 Pi 的概率会掉回树根求它从树根爬到树顶时经过的时间的期望值是多少。
【输入格式】
输入第一行包含一个整数 n 表示树的高度。
接下来 n 行每行包含两个整数 xi,yi用一个空格分隔表示 Pixi / yi。
【输出格式】
输出一行包含一个整数表示答案答案是一个有理数请输出答案对质数 998244353 取模的结果。
其中有理数 a / b 对质数 P 取模的结果是整数 c 满足 0≤cP 且 c⋅b≡a(modP)。
【数据范围】
对于 20% 的评测用例n≤21≤xiyi≤20 对于 50% 的评测用例n≤5001≤xiyi≤200 对于所有评测用例1≤n≤1000001≤xiyi≤10的9次方为了保证不出现无解的情况额外增加限制条件 yi−xi≠998244353如不增加此条件则可能出现无解情况此为比赛原题考虑不周。
【输入样例1】 1 2 【输出样例1】 2 【输入样例2】 3 1 2 3 5 7 11 【输出样例2】 623902744 【代码】
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL;const int P 998244353;int n;LL qmi(int a, int b)
{LL res 1;while (b){if (b 1) res res * a % P;a (LL)a * a % P;b 1;}return res;
}int main()
{scanf(%d, n);int res 0;while (n -- ){int x, y;scanf(%d%d, x, y);res (res 1ll) * y % P * qmi(y - x, P - 2) % P;}printf(%d\n, res);return 0;
}
