基本容斥

[ABC066D] 11

首先如果没有重复的数，答案肯定是 \(C_n^k\)。

考虑如何加入有重复的数这一性质。
不难想到用容斥思想，减去重复的部分。

那么考虑那些数列可能会重复：显然如果 \(x\) 出现了两次并且分别出现在 \(y1\)，\(y2\)，那么重复了的数列中一定不会出现下标在 \((y1,y2-1)\) 中（默认 \(y1<y2\)），所以就相当于在剩下的数中选出 \(k\) 个数。

code

[SDOI2016] 排列计数

首先考虑 \(m=0\)的情况，可以发现这个东西就是一个错位排列。

错位排列公式推导：

考虑容斥，不难想到用 \(n!\) 减去只有某个 \(i\) 使得 \(a_i=i\)，再加上有两个数满足 \(a_i=i\)，以此类推。

设 \(d_n\) 表示 \(n\) 的错位排列个数，所以得到式子：

\[d_n=n!+\sum_{i=1}^{n}{(-1)^i A_n^i} \]

然后进行化简：

\[d_n=n!+\sum_{i=1}^{n}{(-1)^i \frac{n!}{i!}} \]

\[d_n=n!+n!\sum_{i=1}^{n}{(-1)^i \frac{1}{i!}} \]

然后对于 \(d_i\) 维护与 \(d_{i-1}\) 的贡献差即可。

不过直接 dp 貌似更常用

然后就直接算出在 \(n\) 个数中选择 \(m\) 个数的方案，然后对于每个方案的代价就是将那 \(m\) 个数去掉后的错位排列数量。

code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e6 + 5, kM = 1e9 + 7;

LL f[kMaxN] = {1}, p[kMaxN] = {1}, n, m, t;

LL P(LL x, LL y) {
  LL ans = 1;
  for (int i = 1; i <= y; i <<= 1, x = x * x % kM) {
    (y & i) && (ans = ans * x % kM);
  }
  return ans;
}

LL V(int x, int y) {
  return p[x] * P(p[y], kM - 2) % kM * P(p[x - y], kM - 2) % kM;
}

void C() {
  cin >> n >> m;
  cout << V(n, m) * f[n - m] % kM << "\n";
}

int main() {
  f[2] = 1;
  for (int i = 1; i < kMaxN; i++) {
    p[i] = p[i - 1] * i % kM;
  }
  for (int i = 3; i < kMaxN; i++) {
    f[i] = (i - 1) * (f[i - 1] + f[i - 2]) % kM;
  }
  for (cin >> t; t; t--) {
    C();
  }
  return 0;
}

咕咕咕