3746. 钢琴演奏家

分享一个PyPy3的代码

p = 1000000007

def fastExpMod(b, e):
    result = 1
    while e != 0:
        if (e&1) == 1:
            result = (result * b) % p
        e >>= 1
        b = (b*b) % p
    return result

for _ in range(int(input())):
    n, m = map(int, input().split())
    com = [0]*(n+1)
    com[m] = 1
    for i in range(m+1, n+1):
        com[i] = ((i*com[i-1]%p)*fastExpMod(i-m, p-2))%p
    L = [int(i) for i in input().split()]
    L.sort()
    L = [0]+L
    res = 0
    for i in range(n, m-1, -1):
        res = (res+(((com[i]-com[i-1])*L[i])%p))%p
    print(res)

很多人要看AC代码，我就挂一个，具体解释看我博客https://blog.csdn.net/qq_43765333/article/details/105003548
代码如下：

include

using namespace std;
typedef long long ll;
const int N=1e6+5;
const ll mod=1e9+7;
ll a[N],F[N],I[N];
ll f(ll a,ll b)//快速乘
{
ll k=0;
while(b)
{
if(b&1) k=(k+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return k;
}

ll power(ll a,ll b){return b?power(aa%mod,b/2)(b%2?a:1)%mod:1;}
void init(){
F[0]=1;
ll s=1;
for(int i=1;i<=N;i++){
s=f(s,i);
F[i]=s;
}
I[N]=power(F[N],mod-2);
for(int i=N;i–;){
I[i]=f(I[i+1],i+1);
}
}

ll C(ll n, ll k){
return f(f(F[n],I[n-k]),I[k]);
}

inline ll read() {
ll s = 0, w = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == ‘-‘) w = -1;
for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
return s * w;
}

int main(){
int t;
t=read();
init();
while(t–){
int n,m;
ll ans=0,cnt=1,sum=0;
n=read();m=read();
for(int i=0;i<n;i++){
a[i]=read();
sum=(sum+a[i])%mod;
}
sort(a,a+n);
for(int i=m-1;i<n;i++){
ans=(ans+f(a[i],C(i,m-1)))%mod;
}
if(m==1) printf(“%lld\n”,sum);
else printf(“%lld\n”,ans);
}
return 0;
}