题目描述

给出一个长度为n的序列，你需要计算出所有长度为k的子序列中，除最大最小数之外所有数的乘积相乘的结果

输入描述:

第一行一个整数T，表示数据组数。 对于每组数据，第一行两个整数N，k，含义如题所示 接下来一行N个整数，表示给出的序列 保证序列内的数互不相同

输出描述:

对于每组数据，输出一个整数表示答案，对

取模 每组数据之间以换行分割 链接： 来源：牛客网

输入

34 3 5 3 1 45 43 7 5 2 110 3 100 1020 2050 102 12 235 4 57 32135 54354

输出

14481000521918013

说明

第一组数据解释

所有长度为3的子序列为

最终答案为

备注:

的数据：

保证序列中的元素互不相同且

，

 

 

 

 题解：

一眼看过去是n^2

二眼看过去要算每一个数的贡献

三眼看过去就是每一个数出现次数

四眼看过去总次数是C(n-1,k-1)

五眼看过去还要容斥，减去作为最大最小值次数

六眼看过去可以排个序，和前面搭配是作为最大值，和后面搭配作为最小值

七眼看过去还要一个快速幂

 

然后手打，结果挂了。AK失败。

好吧，其实方法一点没错，但是细节出了问题。

组合数n^2预处理嘛，习惯性对p=1e9+7取模。

以前一直是这样。。。

 

但是，以前组合数是乘数，现在组合数可是指数啊！！

指数怎么能对p取模呢？？

 

但是指数可以对p-1取模。

因为这里p是质数，a^(p-1)=1 mod p（费马搞死你）

所以，指数减掉若干个p-1，并不影响。

当一般地，(a,p)=1而p不是质数，就欧拉定理，a^(phi(p))=1 mod p呗

 

 

（学信竞1年来，头一次知道对指数取模可以mod phi(p) -_-||）

Code：

#include
        
         #define int long longusing namespace std;const int N=2005;const int mod=1e9+7;typedef long long ll;int n,q,k;ll a[N];ll c[N][N];ll qm(ll x,ll y){    ll ret=1;    while(y){        if(y%2==1) ret=(ret*x)%mod;        x=(x*x)%mod;        y/=2;    }    if(ret<0) ret=(ret+mod)%mod;    return ret%mod;}signed main(){    for(int i=0;i<=2001;i++){     c[i][0]=1;     for(int j=1;j<=i;j++){         c[i][j]=(c[i-1][j-1]+c[i-1][j])%(mod-1);     }    }    scanf("%lld",&q);    while(q--){        scanf("%lld%lld",&n,&k);        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);        sort(a+1,a+n+1);        ll ans=1;        for(int i=1;i<=n;i++){            ll ci=(c[n-1][k-1]-c[i-1][k-1]-c[n-i][k-1]+2*(mod-1))%(mod-1);                        ans=(ans*qm(a[i],ci))%mod;        }        printf("%lld\n",ans);    }    return 0;}
        

 

 注意取余运算的正确性，不是随便瞎取模都行的，也不是一定都对p取模