A4921 | 偶数Ⅱ
时间限制3s
内存限制256MB
通过 / 提交0/0
题目描述
*注:本题与偶数 $Ⅰ$ 题面相同，只有数据范围不同。*
我们定义一个正整数的"美丽度"为该正整数转换为二进制表示后末尾连续 $0$ 的个数。例如，正整数 $4$ 转换为二进制是 $100$，所以它的美丽度为 $2$。
现在，我们引入一个函数 $f(a, b, c)$，其定义如下：
$$f(a, b, c) = \left| a^c - b^c\right|$$
有趣的是，我们发现通过这个函数，可以将三个奇数的运算结果变为偶数。
最近，Alice 听闻你在数学方面造诣颇深，于是她向你求助，希望你能帮忙解决这样一个问题：从前面 $n$（$n\in \mathbf{N}^*$ 且 $n \geq 3$）个正奇数中任意选取三个互不相同的数 $a$、$b$、$c$ ，求 $f(a, b, c)$ 的美丽值的期望值。
我们定义一个正整数的"美丽度"为该正整数转换为二进制表示后末尾连续 $0$ 的个数。例如，正整数 $4$ 转换为二进制是 $100$，所以它的美丽度为 $2$。
现在，我们引入一个函数 $f(a, b, c)$，其定义如下：
$$f(a, b, c) = \left| a^c - b^c\right|$$
有趣的是，我们发现通过这个函数，可以将三个奇数的运算结果变为偶数。
最近，Alice 听闻你在数学方面造诣颇深，于是她向你求助，希望你能帮忙解决这样一个问题：从前面 $n$（$n\in \mathbf{N}^*$ 且 $n \geq 3$）个正奇数中任意选取三个互不相同的数 $a$、$b$、$c$ ，求 $f(a, b, c)$ 的美丽值的期望值。
输入格式
每个测试输入包含多个测试用例。输入的第一行包含一个正整数 $t$ ，表示测试用例的组数。测试用例的描述如下：
每个测试用例的唯一一行包含一个正整数 $n$ ，$n$ 的意义见题目描述。
每个测试用例的唯一一行包含一个正整数 $n$ ，$n$ 的意义见题目描述。
输出格式
对于每个测试用例，打印一个单一的整数，即 $p\cdot q^{-1}\mod 998244353$ 的值。
输入输出样例
输入 #1
2 999 10000
输出 #1
787175672 465614473
数据范围
- $1\le t\le 10^6$
- $3\le n\le 10^6$
经过严谨的数学证明可知，该期望值的答案能够表示为最简分数形式 $\dfrac{p}{q}$，其中 $p$ 和 $q$ 均为整数，并且 $q$ 满足 $q\not\equiv 0\pmod{998244353}$。请你计算并输出一个满足 $p\cdot q^{-1}\mod 998244353$ 的整数。也就是说，输出一个整数 $x$，使得 $0\leq x\lt 998244353$ ，并且 $x\cdot q\equiv p\pmod{998244353}$。
提示：依据费马小定理，有 $q^{-1}\equiv q^{998244351}\pmod{998244353}$。
- $1\le t\le 10^6$
- $3\le n\le 10^6$
经过严谨的数学证明可知，该期望值的答案能够表示为最简分数形式 $\dfrac{p}{q}$，其中 $p$ 和 $q$ 均为整数，并且 $q$ 满足 $q\not\equiv 0\pmod{998244353}$。请你计算并输出一个满足 $p\cdot q^{-1}\mod 998244353$ 的整数。也就是说，输出一个整数 $x$，使得 $0\leq x\lt 998244353$ ，并且 $x\cdot q\equiv p\pmod{998244353}$。
提示：依据费马小定理，有 $q^{-1}\equiv q^{998244351}\pmod{998244353}$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？