给定一个整数从0到N的数组，有多少种方式可以使array [i]不能为i [英] Given an array with integer 0 to N, how many ways to arrange it such that array[i] cannot be i

问题描述

给出一个从0到N的整数的数组，有多少种排列方式，使得在数组的位置i上不能插入i?

Given an array with integer 0 to N, how many ways to arrange it such that at position i of the array, we cannot have i inserted in it?

例如，N = 2

以下安排有效:

• 1,2,0
• 2,0,1

• 1,2,0
• 2,0,1

因此，答案是2种安排

我想不出一种非蛮力方法在O(1)时间内做到这一点，有人可以帮我吗?

I can't think of a non-brute force method to do this in O(1) time, can anyone help me out?

推荐答案

这种排列称为 derangement . Wiki页面包含许多公式来对其进行计数.例如，重复发生:

Such kind of permutations is called derangement. Wiki page contains a lot of formulas to count them. For example, recurrence:

!n=(n-1)(!(n-1)+!(n-2))

其中，!n(称为子因子)表示排列的数量，起始值为!0 = 1和!1 = 0

where !n, known as the subfactorial, represents the number of derangements, with the starting values !0 = 1 and !1 = 0

这篇关于给定一个整数从0到N的数组，有多少种方式可以使array [i]不能为i的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！