弹钢琴

这是一道裸的求组合数的题目
一共有两种写法
一种是用dp递推组合数
公式为$C[i][j]=C[i][j-1]+C[i-1][j-1]$ i表示一共有几个数，j表示取几个数
复杂度为n*m
代码实现：

sort(A+1,A+n+1);
dp[0][0]=1;
long long ans=0;
FOR(i,1,n) { 
    FOR(j,1,m) { 
        dp[i][j]+=dp[i-1][j-1]+dp[i-1][j];
        if(dp[i][j]>=Mod)dp[i][j]-=Mod;
}
    ans+=1LL*(dp[i][m]%Mod*A[i])%Mod;
    ans%=Mod;
}
printf("%lld\n",ans);

另外一种是用乘法逆元求组合数，由于在求组合数时边乘边模边除会出错，
是用乘法逆元可化除法为乘法，
公式为$C[i][j]=C[i-1][j]*i*(i-j)^{mod-2}$
由于$(i-j)^{mod-2}$可以预处理出来，所以递推的复杂度为O(n)
预处理的复杂度O(nlogn) 带快速幂

代码实现：

FOR(i,1,n)B[i]=fast(i,Mod-2);
C[k-1]=1;
FOR(i,k,n-1)C[i]=1LL*C[i-1]*i%Mod*B[i-k+1]%Mod;
ll ans=0;
sort(A+1,A+n+1); 
FOR(i,k,n){ans+=1LL*C[i-1]*A[i]%Mod;ans%=Mod;
}

ps:这里应该是选定第i个然后在i-1个物品中取k-1个

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！