F-子序列

题目描述
给出一个长度为n的序列,你需要计算出所有长度为k的子序列中,除最大最小数之外所有数的乘积相乘的结果
题目链接:https://www.nowcoder.com/acm/contest/181/F

就是考虑每个数的贡献,感觉好多题都是考虑单独的贡献,可是我还是没养成这种思维T_T

每个数的贡献就是:每次的选择都有他-他作为最大-他作为最小
先排序,考虑第 i 个数
①每次选择都有这个数的次数:先把他选了,然后在剩下 N 1 个数中随便选 K 1 个数,那么就是 C N 1 K 1
②这个数作为最大:先把他选了,然后在剩下 i 1 个比他小的数中选 K 1 个,就是 C i 1 K 1
③这个数作为最小:先把他选了,然后在剩下 N i 个数中选 K 1 个数,就是 C N i K 1

但是这是指数上的取模,我说怎么都是用的递推式来求组合数。。。结果是因为他在指数上,取个欧拉函数就不互质了。。。

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=1e3+5;
const int MOD=1e9+7-1;//因为是在指数上降幂,用他的欧拉函数 
LL com[maxn][maxn]={1};
LL ksm(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1)res=(res*base)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}
LL fac[maxn]= {1,1},invf[maxn]= {1,1};
void InitFac(int n)
{
    for(int i=0;i<=1000;i++)com[i][0]=com[i][i]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {
            com[i][j]=(com[i-1][j-1]+com[i-1][j])%MOD;
        }
    }
}
LL C(int n,int m)
{
    if(n<=0||n<m)return 0;
    return com[n][m];
}
LL N,K;
LL a[maxn];
int main()
{
    InitFac(1000);
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%lld%lld",&N,&K);
        for(int i=1;i<=N;i++)scanf("%lld",a+i);
        sort(a+1,a+1+N);
        LL ans=1;

        for(int i=1;i<=N;i++)
        {
            LL tp=C(N-1,K-1);//所有情况
            tp-=C(i-1,K-1);//第i个数作为最大,然后在比他小的前i-1个数中选k-1个数
            tp-=C(N-i,K-1);//第i个数作为最小,然后在比他大的后面N-i个数中选k-1个数 
            tp=(tp%MOD+MOD)%MOD;
            ans*=ksm(a[i],tp,MOD+1);
            ans%=(MOD+1);
        }
        cout<<ans<<endl;
    }
}