2022寒假牛客训练4

G-子序列权值乘积
设计知识： 欧拉降幂
如果我们要求ab%p 而b是一个很大的数，可以先将b对p-1取模，不会影响结果的正确性，前提是a和p互质。

这一题我们可以将数字先进行排序，因为子序列中只有最大和最小的才会被计算，那我们不妨将某个数 ai 取作这个序列中的最值，剩下的全部取比 ai 小或大的数，那么就可以转换成算 ai 前面数的组合数加上 ai 后面数的组合数 然后加上只取 ai 时会被算两遍的情况即可。

#include <bits/stdc .h>
#define N 200005
using namespace std;

const long long mod = 1000000007;

long long quick_power(long long base, long long power, long long mod)
{
long long result = 1;
base %= mod;
while (power)
{
if (power & 1)
{
result = (result * base) % mod;
}
power >>= 1;
base = (base * base) % mod;
}
return result;
}
long long a[N];

int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int n;
long long ans = 1;
cin >> n;
for (int i = 1; i <= n; i )
cin >> a[i];
sort(a 1, a n 1);
for (int i = 1; i <= n; i )
{
long long l, r;
//此处模取mod-1 用了欧拉降幂
// l r为左侧组合数加上右侧组合数加上ai取两次的情况（也就是ai被乘的次数）
l = quick_power(2, i - 1, mod - 1);
r = quick_power(2, n - i, mod - 1);
ans *= quick_power(a[i], (l r) % (mod - 1), mod);
ans %= mod;
}
cout << ans;
return 0;
}

这篇好文章是转载于：学新通技术网