前言
来篇 atcoder 的题解欧~
题意
有两个包含 \(n\) 个数字的序列 \(A\) 、 \(B\) ,满足一下条件:
- \(1\leq A_i,B_i\leq m,(i\in[i,n])\)
- \(A_i\neq B_i,(i\in[i,n])\)
- \(A_i\neq A_j(1\leq i<j\leq n)\)
给定 \(n\) , \(m\) ,且 \(n\leq m\) ,求合法的方案数。
两种不同的方案,当且仅当序列 \(A\) 不同或序列 \(B\) 不同。
两个序列不同,当且仅当 \(\forall i,j\leq n,a[i]\neq a[j]\) 。
思路
错排问题的变式。
首先来说明错排问题的递推解法:\(dp[i]=(i-1)(dp[i-1]+dp[i-2])\) 。
其中, \(dp[i]\) 为 \(1\) ~ \(i\) 的错排方案数。
证明:对于第 \(n\) 个加入的数字,有 \(n-1\) 种放发(不能够放在位置 \(n\) 上)。
对于每一个 \(k\) 不与 \(n\) 相等,将 \(n\) 放在位置 \(k\) ,有两种情况。
- \(k\) 放在位置 \(n\) 上,则相当于不管 \(n\) 和 \(k\) ,然后剩下的 \(n-2\) 个数字错排,有 \(dp[i-2]\) 种情况。
- \(k\) 没有放在位置 \(n\) 上,因为 \(k\) 不能放在位置 \(n\) 上,所以就相当于不包括数字 \(n\) 的错排,有 \(dp[i-1]\) 种情况。
我们首先固定序列 \(A\) ,选出 \(n\) 个数字,则共有 \(A_m^n\) 种方案。则对于这 \(A_m^n\) 种方案,所选出的 \(B\) 构成的合法方案都不同,那么就只用针对一个典型的案例来进行研究就行了。
则问题就可以转换为:加入 \(n\) 个数字使得这些数字都在 \(1\) ~ \(m\) 内,且互不相同,且满足:\(i\) 不在位置 \(i\) 上,\(i\in[1,n]\)。
我将这个问题称之为“假错排”。
“假错排”就是在上述的情况上加上一种情况:
- 对于第 \(n\) 个加入的数字,将任意一个数字 \(k(k\in[1,m],k\notin A)\) 填入位置 \(n\) 。
则可以得到状态转移方程:\((m-n)dp[i-1]+(i-1)(dp[i-1]+dp[i-2])\) 。
然后这道题就做完了。
Code
时间复杂度为 \(O(n)\) ,代码很短。
#include <cstdio>
#define int long long
const int MAXN = 5e5 + 5;
const int MOD = 1e9 + 7;
int dp[MAXN], n, m, ans;
signed main() {
scanf("%lld %lld", &n, &m);
dp[0] = 1;
dp[1] = m - n;
for(int i = 2; i <= n; i++)
dp[i] = ((m - n) * dp[i - 1] % MOD + (i - 1) * (dp[i - 2] + dp[i - 1]) % MOD) % MOD;
ans = dp[n];
for(int i = m, j = 1; j <= n; i--, j++)
ans = (ans * i) % MOD;
printf("%lld", ans);
return 0;
}