zhangjinxuan 发表于 2023-10-2 16:24
祝你能得更多的分！
我尽力
申请问问题:样例2的11/36是怎么算出来的？
sfqxx 发表于 2023-10-2 19:56
申请问问题:样例2的11/36是怎么算出来的？
一次对的概率是1/6，错的概率是5/6；如果两次的话，至少一次对相当于去除两次全错的概率就可以了，两次全错的概率是（5/6）^2，就是25/36，1-25/36就是至少一次成功的概率，也就是11/36
zhangjinxuan 发表于 2023-9-23 14:08
@sfqxx @Ewan-Ahiouy @liuhongrun2022 @学习编程中的Ben @额外减小 @tommyyu @柿子饼同学 @陈尚涵 @zsy0226 ...
国庆快乐
liuhongrun2022 发表于 2023-10-2 12:39
比赛榜单 24 小时没变化了，确认结束比赛（若一人否决该条不通过）？
并不，我要再试试
这两天出去玩没空看，接下来的两天再看看，还能再得点分，名次能不能提高不一定了；题都能解出来，下异步主要是时间复杂度的问题。
hao7608 发表于 2023-10-2 20:54
一次对的概率是1/6，错的概率是5/6；如果两次的话，至少一次对相当于去除两次全错的概率就可以了，两次全 ...
谢谢。
hao7608 发表于 2023-10-2 21:00
这两天出去玩没空看，接下来的两天再看看，还能再得点分，名次能不能提高不一定了；题都能解出来，下异步 ...
那样例3呢(
我在外面，我比不了
比赛没了！！！！
加油
@FishC 如何求解如下递推式第 $n$ 项的值 $f_i=af_{i-1}+(i\bmod b)+c$，$f_1=d$，其中 $a,b,c,d$ 为给定的常数，答案对 $998244353$ 取模。
zhangjinxuan 发表于 2024-11-20 21:46
@FishC 如何求解如下递推式第 $n$ 项的值 $f_i=af_{i- ...
我们可以通过直接模拟递推关系来解决这个问题。以下是解题思路：
1. 初始化初始条件，$f_1 = d$。
2. 从第 2 项开始递归计算到第 $n$ 项。对于每一项 $f_i$，根据递推式进行计算：
\[
f_i = a \cdot f_{i-1} + (i \bmod b) + c
\]
3. 因为题目要求答案对 $998244353$ 取模，所以在每一次计算完 $f_i$ 后，进行取模操作：
\[
f_i = f_i \bmod 998244353
\]
整个过程只需要遍历计算 $n$ 项，时间复杂度是 $O(n)$，能够在合理时间内解决。
以下是伪代码实现：
input a, b, c, d, n
modulo = 998244353
f = * (n + 1)
f = d
for i from 2 to n:
f = (a * f + (i % b) + c) % modulo
output f
确保在循环中的计算过程中每一步都对 $998244353$ 取模，以防止整数溢出或计算结果不符合取模的要求。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
FishC 发表于 2024-11-20 21:51
input a, b, c, d, n
modulo = 998244353
f = * (n + 1)
你这代码是个人都会啊？？？$n\le10^{10}$ 咋做，能优化吗
zhangjinxuan 发表于 2024-11-20 22:06
你这代码是个人都会啊？？？$n\le10^{10}$ 咋做，能优 ...
要解决这个问题，我们需要寻找递推式的数学规律，而不是通过简单的循环模拟。由于 $n$ 的最大值可达 $10^{10}$，直接计算每一项显然是不现实的，所以我们要尝试找出递推关系的一般形式。
对于递推式：
\[ f_i = a f_{i-1} + (i \bmod b) + c \]
我们可以通过观察「$(i \bmod b)$」重复的周期性来进行优化。具体步骤如下：
1. **周期分析**：$(i \bmod b)$ 每 $b$ 个数会周期性重复，这意味着对每个完整周期，我们都可以通过求和的方式计算出贡献值。
2. **矩阵快速幂**：通过构建状态转移矩阵，利用矩阵的快速幂来计算递推式。我们可以将递推式转换为矩阵形式，进而通过矩阵快速幂计算第 $n$ 项。
3. **数学归纳**：考虑到具体的常数项运算，我们可以在数学上推导出递推式的一般解公式，进一步减少计算。
通过这些思路，我们可以避免直接对 $n$ 个数进行迭代，从而大幅提升计算效率。具体的代码实现可能较为复杂，需要运用矩阵运算和数论知识来优化计算。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
FishC 发表于 2024-11-20 22:07
要解决这个问题，我们需要寻找递推式的数学规律，而不是通过简单的循环模拟。由于 $n$ 的最大值可达 $1 ...
我设想通过数学归纳法计算，这应该怎么做
zhangjinxuan 发表于 2024-11-20 22:08
我设想通过数学归纳法计算，这应该怎么做
要通过数学归纳法解析该递推式的第 $n$ 项，我们可以尝试在逻辑上推导出一般表达式。以下是如何进行这方面的推理：
1. **初始条件**：
- 首先有 $f_1 = d$。
2. **递推式展开**：
- 根据递推式 $f_i = a f_{i-1} + (i \bmod b) + c$，可以展开如下：
- $f_2 = a f_1 + (2 \bmod b) + c$
- $f_3 = a f_2 + (3 \bmod b) + c$
- $\ldots$
- $f_n = a f_{n-1} + (n \bmod b) + c$
3. **模式识别和归纳假设**：
- 尝试识别一般模式，考虑构建一个假设 $f_i$ 的形式，并通过数学归纳验证。
- 例如，对式子进行展开与化简，找出与等比数列、等差数列等相关的结构。
4. **找到周期**：
- 因为 $(i \bmod b)$ 是周期性的，所以可以在展开过程中分组观察每一完整周期对项的贡献。
5. **归纳证明**：
- 假设我们找到了 $f_i$ 的一般形式 $\Phi(i)$，尝试用数学归纳法验证：
- 对于 $i = 1$，初始条件成立。
- 假设 $f_k = \Phi(k)$ 成立，验证 $f_{k+1} = \Phi(k+1)$ 是否成立，以验证整个逻辑的正确性。
通过这样的数学推理，有可能构建出一个一般公式，进而进行快速计算，从而避免逐项展开和计算。具体推导因涉及复杂数学运算，这里提供一种思路，实际操作可能需要具体计算工具的辅助。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。