abc172e
构造两个长度为n的序列，可选的数在[1..M]范围，要求满足以下条件
- \(A_i\neq B_i\)
- \(A_i\neq A_j\)， \(B_i\neq B_j\)
求方案数
如果两个条件一起考虑会很麻烦，假设不考虑第一个条件，只考虑第二个，答案显然是 \(A_M^N*A_M^N\),现在我们要考虑第一个只需在加上一个容斥即可。
\(\sum_{K=0}^{N}(-1)^KC_N^KA_M^KA_{M-K}^{N-K}A_{M-K}^{N-K}\)
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
const int N=5e5+5;
typedef long long ll;
const ll mo=1e9+7;
ll inv[N],f[N],ans,z;
int n,m;
ll power(ll a,ll b){
ll t=1,y=a;
while (b){
if (b&1) t=t*y%mo;
y=y*y%mo;
b/=2;
}
return t;
}
int main(){
// freopen("data.in","r",stdin);
scanf("%d %d",&n,&m);
f[0]=1;
fo(i,1,m) f[i]=f[i-1]*(ll)i%mo;
inv[m]=power(f[m],mo-2);
fd(i,m-1,1) inv[i]=inv[i+1]*(ll)(i+1)%mo;
inv[0]=1;
fo(k,0,n){
z=f[n]*inv[k]%mo*inv[n-k]%mo;
z=z*f[m]%mo*inv[m-k]%mo;
z=z*f[m-k]%mo*inv[m-n]%mo;
z=z*f[m-k]%mo*inv[m-n]%mo;
if (k&1) ans=(ans-z)%mo;
else ans=(ans+z)%mo;
}
ans=(ans%mo+mo)%mo;
printf("%lld",ans);
return 0;
}