牛客練習賽42 C 出題的訣竅 //快速幂，費馬小定理，容斥思想

牛客練習賽42 C 出題的訣竅  //快速幂，費馬小定理，容斥思想

https://ac.nowcoder.com/acm/contest/393/C

 将相同的數字(a)出現的次數(p)求出來，那麼p個a對答案的貢獻就是a*X(包含ai的種數)

其中     X=所有組合的種數(m^n）- 不含ai的種數

∑所有數字對答案的影響     就是答案。

求m的逆元的時候用到費馬小定理的推論。inv(a,mod) = pow(a,mod-2)  (當mod為素數時)。

瞎扯了半天也沒想到這個結論（trl）。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mod 1000000007
 
struct no{
    LL h,val;
}a[4000005];
 
 
bool operator<(const no &x,const no &y){
    if(x.val==y.val){
        return x.h<y.h;
    }
    return x.val<y.val;
}
LL quick_mod(LL aqa,LL  nqn,LL mood)
{
    LL re=1;
    while(nqn){
        if(nqn&1){
            re=(re*aqa)%mood;
        }
        aqa=(aqa*aqa)%mood;
        nqn>>= 1;
    }
    return re;
}
int main(){
    ios::sync_with_stdio(false);
    LL n,m;
    cin>>m>>n;
    LL mpn=quick_mod(m,n,mod);
    LL in=quick_mod(m,mod-2,mod);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int xxx=(i-1)*m+j;
            cin>>a[xxx].val;
            a[xxx].h=i;
        }
    }
    sort(a+1,a+1+m*n);
    a[m*n+1].val=INT_MAX;
    LL ans=0;
    for(int i=1;i<=m*n;){
        LL te=mpn,nowv=a[i].val;
        for(int j=i;j<=m*n;){
            LL xxx=1;
            for(int k=j;k<=m*n;k++){
                if(a[k].val==a[k+1].val&&a[k].h==a[k+1].h) ++xxx;
                else {
                    j=k+1;
                    break;
                }
            }
            te=te*(m-xxx)%mod*in%mod;
            if(a[j].val!=a[j-1].val){
                i=j;
                break;
            }
        }
        ans=(ans+(mpn-te)%mod*nowv%mod)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}