[已解决]梦想星际舰队第16关 && FCOI #8 第三题绳子题解【原创】

zhangjinxuan

梦想星际舰队第16关 && FCOI #8 题解

第三题：绳子

题目描述
有 N 个物品，现在要用一些绳子把它们连起来，使得两个物品之间都有一根绳子链接。

一根绳子只能连接 2 个物品。

答案可能过大，请输出结果对 10^9+7 取模的结果。

输入格式
一行一个整数 N。

输出格式
一个整数表示答案。

输入输出样例
输入 #1

1. 4

复制代码

输出 #1

1. 6

复制代码

输入 #2

1. 10

复制代码

输出 #2

1. 45

复制代码

输入 #3

1. 114514

复制代码

输出 #3

1. 556670799

复制代码

数据范围
对于 30% 的数据，保证 1≤N≤1000

对于 100% 的数据，保证 1≤N≤10^6


Extra 数据范围
对于 100% 的数据，保证 1≤N≤10^18

其他说明
本题目为 zhangjinxuan 原创题目。
测试链接：https://www.luogu.com.cn/problem/U325335

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士排行榜

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳答案

月排行榜 / 总排行榜

Ewan-Ahiouy

2023-8-22 21:13:02

1. def r(n):
   
2.         return n * (n - 1) // 2
   
3. n = int(input())
   
4. print(r(n) % 1000000007)

复制代码

最佳我来啦~

跳转到最佳答案楼层

陶远航

1. k = int(input())
   
2. print(int((1 + k - 1) * (k - 1) / 2 % (10 ** 9 + 7)))

复制代码

isdkz

这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[ i]表示连接i个物品所需的绳子的数量。

首先，我们考虑边界情况。当只有一个物品时，不需要绳子，即dp[1] = 0。当有两个物品时，需要一根绳子，即dp[2] = 1。

接下来，我们考虑连接i个物品所需的绳子的数量。我们可以将第i个物品与前面的任意一个物品连接，然后将剩下的i-1个物品连接起来。因此，dp[ i] = dp[i-1] + (i-1)。

最后，我们将结果对10^9+7取模，即dp[N] % (10^9+7)。

下面是具体的代码实现：

1. def solve(N):
   
2.     dp = [0] * (N+1)
   
3.     dp[1] = 0
   
4.     dp[2] = 1
   
5.     for i in range(3, N+1):
   
6.         dp[ i] = (dp[i-1] + (i-1)) % (10**9+7)
   
7.     return dp[N]
   
8. 
   
9. N = int(input())
   
10. print(solve(N))
    

复制代码

希望能帮到你！

zhangjinxuan

isdkz 发表于 2023-8-22 21:06
这个问题可以使用动态规划来解决。我们定义一个数组dp，其中dp[ i]表示连接i个物品所需的绳子的数量。

...

呃呃，小题大作了吧

Ewan-Ahiouy

1. def r(n):
   
2.         return n * (n - 1) // 2
   
3. n = int(input())
   
4. print(r(n) % 1000000007)

复制代码

最佳我来啦~

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-22 21:13
最佳我来啦~

bushi，这是绳子

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-22 21:15
bushi，这是绳子

你的链接错了！！！害得我丢人

Ewan-Ahiouy

(1 + k - 1)不就等于k吗

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-22 21:16
(1 + k - 1)不就等于k吗

？

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-22 21:17
？

我的帖子改了

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-22 21:18
我的帖子改了

已处理~

继续水梦想护卫舰的业绩

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-22 21:19
已处理~

继续水梦想护卫舰的业绩

测试链接错了

zhangjinxuan

Ewan-Ahiouy 发表于 2023-8-22 21:19
测试链接错了

改了

Ewan-Ahiouy

zhangjinxuan 发表于 2023-8-22 21:20
改了

6，无权查看

Ewan-Ahiouy

陶远航是真恶心，我发问题他抄题解，这个这么简单的问题照样抄，还有那个封号事件

sfqxx

Ewan-Ahiouy 发表于 2023-8-22 21:28
陶远航是真恶心，我发问题他抄题解，这个这么简单的问题照样抄，还有那个封号事件

1c

unsigned_int

好多这个系列