一流的基础微网站开发,公司的网站建设费进入什么科目,手游网站建设方案预算,为什么打开谷歌浏览器是2345网址导航【题目描述】
有一只甲壳虫想要爬上一棵高度为 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;
}
