遇到一个计数问题，求解答
一天 Tom 在上手工课，老师给他们每个人发了一个白色的纸条，上面有 n 个方格 (2<=n<=1e6)。然后又给他们每个人发了n-1个彩带，一个彩带可以粘到两个相邻的方格上。现在老师让他们把n个方格都粘上彩带(可以不用完n-1个彩带，一个方格上可以重复粘彩带 )。Tom是一个热爱数学的人，他想知道所有的方案中，一共用了多少次彩带(所有的方案所用的彩带的总和 )。（答案对 1e9+7 取模）输入一个数 n 表示方格的个数。输出一个数表示最终方案数，答案对 1e9+7 取模。
展开
收起
1
条回答
写回答
写回答
-
对于每个方案来说，最少需要n/2个彩带，最多要n-1个彩带，然后我们分别对其进行计算贡献。操作最多i次的方案数是f[i]，恰i次的方案就是f[i]-f[i-1]，而f[i]=C(n-1-I,i-1)。具体含义 : 可以看作是每次可以选择+1,+2, 求构成n-2的方案数 , 我们先默认都+1, 剩下就是选择+0,+1了 , 只要总共的i-1 次操作中有n-1-i 个选择了+1, 就一定可以达到目标了。 因此输入：3 输出：4
2021-12-23 18:57:19赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
