Niuke winter vacation training camp 4 g (enumeration optimization, Euler power reduction)

Because it is a subsequence problem , You can find that there are two choices for each element , Choose or not

So there may be 2^n Seed sequence , If you enumerate all the intervals , And find out their maximum and minimum , The time complexity is O(n*2^n)

Because only the maximum and minimum values of each interval are used , So we just need to enumerate the maximum and minimum values , At the same time, we found that because it is a subsequence , Don't care about his position , Because as the most valuable position, it can be arbitrary , So you can sort

So for every point , There are all cases as the maximum and all cases as the minimum , Because the product is , You can list the number of times he takes as the maximum value p, obtain And the number of times as the minimum q, obtain , Don't worry about the other maximum value matching him

because 2^p and 2^q The time complexity as a power is too high , So we need to use Euler power reduction

number theory --- Euler theorem , Fast power inverse _qq12323qweeqwe The blog of -CSDN Blog

Due to Fermat's small lemma ：

Content ： Existence prime p,a And p Coprime   == 

that q == (p-1)u +v , because a^(p-1)u ==1, So there is one left a^v, So we just need to a Take a module to the power of , You can achieve the effect of power reduction

summary ：

• The nature of the topic , Subsequence + The most value , Find that you don't need to care about the location of elements , You can sort in ascending order
• A number position i, As a minimum    As the maximum value  
• The product of a number  , Carry out Euler power reduction

#include <iostream>
#include <algorithm>
using namespace std;
const int N=2e5+10;
const int mod=1e9+7;
int a[N];
typedef long long ll;
ll qmi(ll a,ll b,ll mod)
{
	ll res=1;
	while(b)
	{
		if(b&1)
			res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	ll res=1;
    sort(a+1,a+1+n);    // The sequence needs to be rearranged 
	for(int i=1;i<=n;i++)
	{
		// As a minimum 
		res=res*qmi(a[i],qmi(2,i-1,mod-1)+qmi(2,n-i,mod-1),mod)%mod;
	}
	cout<<res;
	return 0;
}