糖果店（组合数学）

链接：https://ac.nowcoder.com/acm/contest/8582/F
来源：牛客网

Bob和Jerry 是一对亲密无间的朋友，他们都非常喜欢吃糖果。这一天，他们来到了华东交大ACM集训队的糖果店购买糖果，糖果店中从左到右摆放着n种糖果，第i种糖果有一个美味值a[i]。Bob和Jerry有一个非常奇怪的爱好，他们总是会购买美味值最低的和美味值最高的糖果。除此之外，Bob购买时必定会挑选摆放在一起的糖果,Jerry却没有这个限制。请问Bob和Jerry分别有几种不同的购买方式。如果两种购买方式包含不同种类的糖果，则认为是不同的。

输入描述:

第一行输入数字t，表示接下来将输入t组数据。(t <= 10)

对于每一组数据，会输入两行：

第一行输入数字n，表示糖果店中有n种糖果（N <= 100,000）

第二行输入n个数字，每一个数字都小于等于100000。第i个数字表示第i种糖果的美味值。

输出描述:

分别输出Bob和Jerry购买方式的数目

示例1

输入

复制

输出

复制

1 2
3 6

备注:

第一组数据有三种糖果，美味值最大值为3、最小值为1，Bob可以选择购买第1、2、3种糖果，Jerry可以购买第1、3种糖果或者第1、2、3种糖果，因此答案分别是1和2

第二组种最大值为4，最小值为1.Bob可以选择购买第1、2种或第1、2、3种或第1、2、3、4种。Jerry可以购买第1、2种或第1、2、3种或第1、2、4种或第1、4种或第1、3、4种或第1、2、3、4种。答案分别是3和6。除此之外Bob无法购买第1、4种，因为这两种糖果没有摆放在一起。也无法购买第1、3种，因为没有购买美味值最大的糖果。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map> 
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
const int mod=1e9+7;
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b%2){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b/=2;
    } 
    return ans%mod;
} 
ll a[maxn];
ll n;
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        ll ma=0;
        ll mi=1e18;
        ll ci=0;
        ll cm=0;
        ll cc=0;
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            ma=max(ma,a[i]);
            mi=min(mi,a[i]);
        }
        if(ma==mi){
            ll ans=qpow(2,n)-1;
            printf("%lld %lld
",n,ans);
            continue;
        }    
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(a[i]==ma){ 
                cm++;
            }
            else if(a[i]==mi){
                ci++;
            }
            else{
                cc++;
            }
        }
        ll ans1=0;
        ll p=0;//最小 
        ll z=0;//最大
        ll ans=0;
        for(int i=1;i<=n;i++){
            if(a[i]==mi){
                p=i;
            }
            else if(a[i]==ma){
                z=i;
            }
            ans+=min(p,z);
        }
        ans1=(((qpow(2ll,cm)-1)%mod*(qpow(2ll,ci)-1)%mod)%mod*(qpow(2ll,cc))%mod)%mod;
        printf("%lld %lld
",ans%mod,ans1%mod);
    }
}