牛客寒训营4 G(梅开二度，欧拉降幂又一次不会)

题目 题意: 给定长度为n的数组，求出该数组所有非空子序列的权值的乘积。权值： 该数组的最大值最小值 思路:   首先，观察到每个数都会在非空子序列中出现2^(n-1)次。   之后，发现对于第i小的数，他有2^ (i-1)作为最大值出现，2^(n-i)次作为最小值出现。   sort之后，枚举每个数统计贡献即可。但是发现幂次是2^n，即使用快速幂也要n * logn * n，寄。   根据费马小定理， a^(p-1) % p == 1(a和p互质)。尽管幂次很大，但我们可以去%(p-1)，使得从而将幂次控制在1e9以内。 a ^x, x = k(p-1) + left. a ^ x % p = 1 * a^left. 时间复杂度: O(nlogn) 代码:

// Problem: 子序列权值乘积
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23479/G
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>= 1;
	}
	return res % mod;
}
void solve()
{
   read(n);
   for(int i=1;i