E - NEQ(容斥原理&组合数学)

E - NEQ(容斥原理&组合数学)

传送门

思路：容斥原理+组合数学。

显然要求且数组中元素互异。

所以对于数组，我们要从个数选个数来全排列。

即个数为.

接下来我们考虑每个对于的方案，对于有多少个。

显然这是个一个容斥原理的应用，我们考虑用总方案减去所有不合法的方案数，

枚举不合法的位置个数分别为个对应的方案数，

当不合法的位置有个时，不合法的方案数为：

从个位置中选出个不合法的位置，然后用剩下个数，选出个数进行全排列。

然后用

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int n,m;
ll fac[N],inv[N];
ll ksm(ll a,ll n){
    ll ans=1;
    while(n){
        if(n&1) ans=ans*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return ans;
}
ll C(int m,int n){
    return fac[m]*inv[m-n]%mod*inv[n]%mod;
}
ll A(int m,int n){
    return fac[m]*inv[m-n]%mod;
}
int main(){
    scanf("%d%d",&n,&m); 
    fac[0]=1;
    for(int i=1;i<=m;i++) fac[i]=fac[i-1]*i%mod;//阶乘递推. 
    inv[m]=ksm(fac[m],mod-2);//费马小定理. 
    for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;//阶乘逆元递推. 
    ll ans=0;
    for(int i=0;i<=n;i++){
        ans+=C(n,i)*((i&1)?-1:1)*A(m-i,n-i)%mod;
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n",ans*A(m,n)%mod);
    return 0;
}