题意 : 1到n的排列中前m个中恰好有k个数每个数都和他的下标相同。问这样有几个 ? 答案取模。
思路 : 前m个(1~m)选择k个是组合数C(m, k)种, 然后令x = m - k, y = n - m; 则 x中会有[0, x]个位置是下标和值一样, 这里可以利用容斥原理做,即减去i为奇数的加上i 为偶数的。
ans = C(m, k) * ∑ (C(x, i) * (x + y - i) ! * (-1)^i ) % mod;
题意 : 1到n的排列中前m个中恰好有k个数每个数都和他的下标相同。问这样有几个 ? 答案取模。
思路 : 前m个(1~m)选择k个是组合数C(m, k)种, 然后令x = m - k, y = n - m; 则 x中会有[0, x]个位置是下标和值一样, 这里可以利用容斥原理做,即减去i为奇数的加上i 为偶数的。
ans = C(m, k) * ∑ (C(x, i) * (x + y - i) ! * (-1)^i ) % mod;