济南医院网站建设服务公司,情感营销,建设网站怎么提需求,wordpress评论链接文章目录1. 题目2. 解题1. 题目
在组合数学中#xff0c;如果一个排列中所有元素都不在原先的位置上#xff0c;那么这个排列就被称为错位排列。
给定一个从 1 到 n 升序排列的数组#xff0c;你可以计算出总共有多少个不同的错位排列吗#xff1f;
由于答案可能非常大如果一个排列中所有元素都不在原先的位置上那么这个排列就被称为错位排列。
给定一个从 1 到 n 升序排列的数组你可以计算出总共有多少个不同的错位排列吗
由于答案可能非常大你只需要将答案对 1097 取余输出即可。
样例 1:
输入: 3
输出: 2
解释: 原始的数组为 [1,2,3]。
两个错位排列的数组为 [2,3,1] 和 [3,1,2]。注释:
n 的范围是 [1, 106]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/find-the-derangement-of-an-array 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题 class Solution { //C
public:int findDerangement(int n) {if(n1) return 0;vectorlong long dp(n1, 0);dp[0] 1;dp[1] 0;for(int i 2; i n; i)dp[i] ((i-1)*(dp[i-1]dp[i-2]))%1000000007;return dp[n];}
};class Solution: #py3def findDerangement(self, n: int) - int:if n1:return 0dp [0]*(n1)dp[0] 1dp[1] 0for i in range(2,n1):dp[i] ((i-1)*(dp[i-1]dp[i-2]))%1000000007return dp[n]我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
