每学期的第10周和20周是USYS的学子最为忙碌的时间。在第9周的时候,有位同学不小心利用matrix的后台bug进入了matrix系统,然后发现了程序设计期中考试的试题。 但是,这个同学过了n天后才把这个试题告诉另外一个同学。从知道试题的那一天开始算起,每个得知试题的同学过了n天之后才能将试题告诉另外一个不知道试题的同学,并且在一天内只能和一位同学说。不幸的是,从知道试题的那一天开始算起,过了m天之后,这份试题就会被这个同学忘记。而且,一个人不能在忘记试题那一天及之后的日子里分享试题。 现在给你三个正整数k,n,m,返回在第k天结束后,知道秘密的人数。由于答案可能会很大,请你将结果对1000000007取余后返回。 k:返回在第k天结束后,知道秘密的人数; n:表示每个同学在知道试题后的第n天才能分享试题; m:表示每个同学在知道试题后的第m天就遗忘了这份试题。 注意,第一天有且只有一个同学知道试题。 输入数据范围: 2≤k≤1000 1≤n<m≤k
时间: 2023-06-13 20:05:22 浏览: 52
这道题可以使用动态规划来解决。我们可以用dp[i][j]表示在第i天结束后,有j个人知道了试题。那么我们可以根据题目要求,得到状态转移方程:
dp[i][j] = (dp[i-1][j] * (j-1) + dp[i-n][j-1]) % mod,其中i > n且i <= m
dp[i][j] = (dp[i-1][j] * (j-1)) % mod,其中i > m
上面的状态转移方程中,第一行表示在第i天结束后,有j个人知道了试题,这个j个人中有一个人是在第i-n天知道的。那么这个人在第i天结束后才能分享试题,所以要在第i-n天之后才能分享试题。所以这个人就成为了新的状态dp[i][j]中的一个人。所以dp[i-n][j-1]就是在第i-n天结束后,有j-1个人知道了试题。而这j-1个人中没有那个在第i-n天知道试题的人,所以我们就可以把这个人加入到第i天结束后知道试题的人中。我们要用dp[i-1][j] * (j-1)来表示在第i-n天结束后,已经有j个人知道了试题,但是没有那个在第i-n天知道试题的人,所以我们要用j-1来表示这个人可以是前面已经知道试题的人中的任意一个。
第二行的状态转移方程表示在第i天结束后,有j个人知道了试题,但是这j个人中没有那个在第i-n天知道试题的人,所以我们不能把这个人加入到第i天结束后知道试题的人中。
最终的答案就是dp[k][1]+dp[k][2]+...+dp[k][k]。
时间复杂度为O(k^2),空间复杂度为O(k)。
参考代码如下:
相关问题
python使用pandas库分别读取“小课时间安排.xlsx”中第5周、第10周的时间安排,并输出
好的,以下是读取“小课时间安排.xlsx”中第5周、第10周时间安排的 Python 代码示例:
```python
import pandas as pd
# 读取第5周时间安排
week5 = pd.read_excel("小课时间安排.xlsx", sheet_name="第5周")
print("第5周时间安排:")
print(week5)
# 读取第10周时间安排
week10 = pd.read_excel("小课时间安排.xlsx", sheet_name="第10周")
print("第10周时间安排:")
print(week10)
```
运行上述代码后,会输出“小课时间安排.xlsx”中第5周和第10周的时间安排。其中,`pd.read_excel()`函数用于读取 Excel 文件,`sheet_name`参数指定需要读取的工作表名称。
使用pandas库分别读取“小课时间安排.xlsx”中第5周、第10周的时间安排,并对齐输出
好的,我知道了。以下是代码实现:
``` python
import pandas as pd
# 读取第5周和第10周的时间安排
week5 = pd.read_excel('小课时间安排.xlsx', sheet_name='第5周')
week10 = pd.read_excel('小课时间安排.xlsx', sheet_name='第10周')
# 对齐输出
print('第5周时间安排:')
print(week5)
print('\n第10周时间安排:')
print(week10)
```
这样就可以将第5周和第10周的时间安排分别读取出来,并输出对齐的结果。注意要将数据文件放在代码同一文件夹下,并且需要安装pandas库。