梦想星际舰队第16关 && FCOI #8 第三题绳子题解【原创】
本帖最后由 zhangjinxuan 于 2023-8-22 21:17 编辑梦想星际舰队第16关 && FCOI #8 题解
第三题：绳子
题目描述
有 N 个物品，现在要用一些绳子把它们连起来，使得两个物品之间都有一根绳子链接。
一根绳子只能连接 2 个物品。
答案可能过大，请输出结果对 10^9+7 取模的结果。
输入格式
一行一个整数 N。
输出格式
一个整数表示答案。
输入输出样例
输入 #1
4
输出 #1
6
输入 #2
10
输出 #2
45
输入 #3
114514
输出 #3
556670799
数据范围
对于 30% 的数据，保证 1≤N≤1000
对于 100% 的数据，保证 1≤N≤10^6
Extra 数据范围
对于 100% 的数据，保证 1≤N≤10^18
其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U325335
答案与解析
**** Hidden Message *****
最佳战士排行榜
**** Hidden Message *****
本帖最后由 陶远航 于 2023-8-22 21:18 编辑
k = int(input())
print(int((1 + k - 1) * (k - 1) / 2 % (10 ** 9 + 7))) 本帖最后由 isdkz 于 2023-8-22 21:09 编辑
这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[ i]表示连接i个物品所需的绳子的数量。
首先，我们考虑边界情况。当只有一个物品时，不需要绳子，即dp = 0。当有两个物品时，需要一根绳子，即dp = 1。
接下来，我们考虑连接i个物品所需的绳子的数量。我们可以将第i个物品与前面的任意一个物品连接，然后将剩下的i-1个物品连接起来。因此，dp[ i] = dp + (i-1)。
最后，我们将结果对10^9+7取模，即dp % (10^9+7)。
下面是具体的代码实现：
def solve(N):
dp = * (N+1)
dp = 0
dp = 1
for i in range(3, N+1):
dp[ i] = (dp + (i-1)) % (10**9+7)
return dp
N = int(input())
print(solve(N))
希望能帮到你！ isdkz 发表于 2023-8-22 21:06
这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[ i]表示连接i个物品所需的绳子的数量。
...
呃呃，小题大作了吧{:10_256:} 本帖最后由 Ewan-Ahiouy 于 2023-8-22 21:15 编辑
def r(n):
return n * (n - 1) // 2
n = int(input())
print(r(n) % 1000000007)
最佳我来啦~{:9_236:} Ewan-Ahiouy 发表于 2023-8-22 21:13
最佳我来啦~
bushi，这是绳子 zhangjinxuan 发表于 2023-8-22 21:15
bushi，这是绳子
你的链接错了！！！{:10_244:}害得我丢人{:10_266:} (1 + k - 1)不就等于k吗{:10_257:} Ewan-Ahiouy 发表于 2023-8-22 21:16
(1 + k - 1)不就等于k吗
？ zhangjinxuan 发表于 2023-8-22 21:17
？
我的帖子改了{:10_254:} Ewan-Ahiouy 发表于 2023-8-22 21:18
我的帖子改了
已处理~
继续水梦想护卫舰的业绩{:10_256:} zhangjinxuan 发表于 2023-8-22 21:19
已处理~
继续水梦想护卫舰的业绩
测试链接错了 Ewan-Ahiouy 发表于 2023-8-22 21:19
测试链接错了
改了 zhangjinxuan 发表于 2023-8-22 21:20
改了
6，无权查看 陶远航是真恶心，我发问题他抄题解，这个这么简单的问题照样抄，还有那个封号事件{:9_239:} Ewan-Ahiouy 发表于 2023-8-22 21:28
陶远航是真恶心，我发问题他抄题解，这个这么简单的问题照样抄，还有那个封号事件
1c 好多这个系列
页:
[1]