?

題干：

題目描述

給出一個長度為n的序列，你需要計算出所有長度為k的子序列中，除最大最小數(shù)之外所有數(shù)的乘積相乘的結(jié)果

?

輸入描述:

第一行一個整數(shù)T，表示數(shù)據(jù)組數(shù)。 對于每組數(shù)據(jù)，第一行兩個整數(shù)N，k，含義如題所示接下來一行N個整數(shù)，表示給出的序列保證序列內(nèi)的數(shù)互不相同

輸出描述:

對于每組數(shù)據(jù)，輸出一個整數(shù)表示答案，對取模 每組數(shù)據(jù)之間以換行分割

?

示例1

輸入

復制

3 4 3 5 3 1 4 5 4 3 7 5 2 1 10 3 100 1020 2050 102 12 235 4 57 32135 54354

輸出

復制

144 81000 521918013

說明

?

第一組數(shù)據(jù)解釋

所有長度為3的子序列為

最終答案為

備注:

對于的數(shù)據(jù)： 對于的數(shù)據(jù)： 對于的數(shù)據(jù)： 保證序列中的元素互不相同且，

解題報告：

首先暴力可以n^2。思路就是要算每一個數(shù)的貢獻，也就是每一個數(shù)的出現(xiàn)次數(shù)。

總次數(shù)是C(n-1,k-1)。我們可以枚舉???在前面選了多少個，在后面選了多少個。但是這樣復雜度就成了O(nk)了，，也高不了哪去。所以想個辦法優(yōu)化，不難想到，可以求問題的反面，容斥一下，用總次數(shù)減去作為最大最小值次數(shù)。可以排個序，和前面搭配是作為最大值，和后面搭配作為最小值。

注意，以前組合數(shù)是乘數(shù)，現(xiàn)在組合數(shù)是指數(shù)，不要習慣性對p=1e9+7取模。

指數(shù)可以對p-1取模。因為這里p是質(zhì)數(shù)，a^(p-1)=1 mod p（費馬小定理）

所以，指數(shù)減掉若干個p-1，并不影響。

當一般地，(a,p)=1而p不是質(zhì)數(shù)，就歐拉定理，a^(phi(p))=1 mod p所以對phi(p)取模

AC代碼：

#include<bits/stdc++.h> #define int long long using 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]+5*(mod-1))%(mod-1);ans=(ans*qm(a[i],ci))%mod;}printf("%lld\n",ans);}return 0; }

參考博客：鏈接???????

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 181F】子序列（容斥，组合数，费马小定理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。