FCOI—Round #10 火热报名啦！【原创】【鱼币多多】【FCOI 半周年庆典赛 】

liuhongrun2022

zhangjinxuan 发表于 2023-10-2 16:24
祝你能得更多的分！

我尽力

sfqxx

申请问问题:样例2的11/36是怎么算出来的？

hao7608

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 ...

国庆快乐

hao7608

liuhongrun2022 发表于 2023-10-2 12:39
比赛榜单 24 小时没变化了，确认结束比赛（若一人否决该条不通过）？

并不，我要再试试

这两天出去玩没空看，接下来的两天再看看，还能再得点分，名次能不能提高不一定了；题都能解出来，下异步主要是时间复杂度的问题。

sfqxx

hao7608 发表于 2023-10-2 20:54
一次对的概率是1/6，错的概率是5/6；如果两次的话，至少一次对相当于去除两次全错的概率就可以了，两次全 ...

谢谢。

sfqxx

hao7608 发表于 2023-10-2 21:00
这两天出去玩没空看，接下来的两天再看看，还能再得点分，名次能不能提高不一定了；题都能解出来，下异步 ...

那样例3呢(

学习编程中的Ben

我在外面，我比不了

sfqxx

比赛没了！！！！

六翻了

加油

zhangjinxuan

@FishC 如何求解如下递推式第 $n$ 项的值 $f_i=af_{i-1}+(i\bmod b)+c$，$f_1=d$，其中 $a,b,c,d$ 为给定的常数，答案对 $998244353$ 取模。

FishC

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 = [0] * (n + 1)
f[1] = d

for i from 2 to n:
    f[i] = (a * f[i - 1] + (i % b) + c) % modulo

output f[n]

确保在循环中的计算过程中每一步都对 $998244353$ 取模，以防止整数溢出或计算结果不符合取模的要求。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

zhangjinxuan

FishC 发表于 2024-11-20 21:51
input a, b, c, d, n
modulo = 998244353
f = [0] * (n + 1)

你这代码是个人都会啊？？？$n\le10^{10}$ 咋做，能优化吗

FishC

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 小助理，如未能正确解答您的问题，请继续追问。

zhangjinxuan

FishC 发表于 2024-11-20 22:07
要解决这个问题，我们需要寻找递推式的数学规律，而不是通过简单的循环模拟。由于 $n$ 的最大值可达 $1 ...

我设想通过数学归纳法计算，这应该怎么做

FishC

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 小助理，如未能正确解答您的问题，请继续追问。