题解-Atcoder-172e

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

题面大意

给定 $n,m$，需要构造长度为 $n$ 的整数序列 $A,B$，使得 $A,B$ 中元素两两互异，并且使得 $A,B$ 两序列相同位置的元素值不同，求方案数模上 $10^9+7$ 的值。

解法

肯定是一道数学题。

我们首先考虑方案的计算，正难则反，可以用总情况数减去所有不合法情况数。

什么情况是不合法的呢？

• 数列内元素不互异。
• 数列 $A$ 和 $B$ 在相同位置的元素值相等。

第一种情况，可以通过排列组合排除掉，下文的数列均满足数列中数两两互异。

对于第二种情况，我们可以定义 $T_i$ 为在数列$A$确定的情况下第 $i$ 位与 $A_i$ 相同的数列构成的集合。

那么容易得出 $|T_i| = A^{n-1}_m$ （因为相等的那一位已经确定了，其他位只需要满足互异即可） 。

我们可以直接求出 $\sum^n_{i=1}|T_i|$ 作为不合法情况数吗？显然不行，因为会有重复情况（例如第 $2$，$3$ 位相等的数列既在 $T_2$ 又在 $T_3$ 中）。

那么实际上我们应该求出的不合法情况数是 $\left|\bigcup_{i=1}^nT_i\right|$。

这个式子怎么求呢？我们来考虑下容斥定理。

容斥定理

这一部分是知识铺垫，上文所有的假设和定义均不适用，已经了解这是什么可以跳过。

首先考虑 $A,B$ 两个集合，那么显然当 $A\bigcap B \neq \emptyset$ 时，$|A|+|B| \neq |A\bigcup B|$。

所以要减去其中重复的部分，即 $\left| A\bigcup B\right| =\left| A\right| +\left| B\right| -\left| A\bigcap B\right|$。

那么如果推广到三个集合呢？此时我们发现 $|A\bigcap B\bigcap C|$ 被多减了一次，所以要加回来，即 $|A\bigcup B\bigcup C|=|A|+|B|+|C|-|A\bigcap B|-|B\bigcap C|+|A\bigcap B\bigcap C|$。

将其推广到任意集合，我们发现如下定理：

$n$ 个集合的并的元素数量等于它们的数量和减去其中任意两个集合的交的数量和加上其中任意三个集合的交的数量和减去其中任意四个集合的交的数量和，以此类推。

好，讲完了，现在我们来看看上面的不合法情况数怎么处理。

那么 $\left|\bigcup_{i=1}^nT_i\right|$ 和这个式子等价：

但是交集也不好算，我们需要再次转化。

想一想，这些集合的交集代表什么？应该代表的是符合这些集合共同特征的数列构成的集合，即上面公式中 $n$ 个集合的交就是有且仅有 $n$ 位与 $A$ 数列相等的数列构成的集合。

我们再做如下定义：定义 $F_i$ 为有且仅有 $i$ 位与 $A$ 相等的序列构成的集合。

现在只要推出 $F_i$，问题就解决了。

那么因为我们需要 $i$ 位相等，那么需要选出 $i$ 位（无顺序要求）来和 $A$ 的每一位匹配，有 $C^i_n$ 种，剩下的位置不能是 $A_i$ 且两两互异，所以有 $A_{m-i}^{n-i}$ 种类。

根据乘法原理可得 $|F_i| = C_n^i \times A_{m-i}^{n-i}$。

这里不要忘记上面的所有公式前提都是在 $A$ 已经确定的情况下推出的，所以答案要乘上 $A^n_m$。

因为我们计算的是不合法方案数，所以我们要用 $A^n_m$ 减去合法方案数。

现在我们整理一下公式：

由于要取模，记得计算乘法逆元。

可以看这里：乘法逆元 - OI Wiki (oi-wiki.com)。

这里只需要知道 $a\times inv(b,p) \equiv a/b\space\text{(mod p)}$。

代码如下：

#include <stdio.h>
#include <ctype.h>
#define mod 1000000007
#define int long long
int pow(int x, int p)
{
  int res = 1;
  while (p)
  {
    if (p & 1)
      res = res * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return res;
}

int inv(int x)
{
  if (x == 0 || x == 1)
    return 1;
  return pow(x, mod - 2) % mod;
}

int n, m, jc[1000007];

int lm(int x)
{
  return (x % mod + mod) % mod;
}

int A(int m, int n)
{
    return lm(jc[n] * inv(jc[n - m]));
}

int C(int m, int n)
{
    return lm(lm(jc[n] * inv(jc[m])) * inv(jc[n - m]));
}

int anm, sum, tval, pv = -1;
signed main()
{
  scanf("%lld%lld", &n, &m);
  jc[0] = 1;
  for (int i = 1; i <= 1000000; i++)
    jc[i] = i * jc[i - 1] % mod;

  for (int i = 1; i <= n; i++)
  {
    tval = lm(lm(C(i, n) * A(n - i, m - i)) * pv);
    sum = lm(sum + tval);
    pv *= -1;
  }

  sum = lm(sum + A(n, m));
  sum = lm(sum * A(n, m));

  printf("%lld\n", sum);

  return 0;
}