东莞非凡网站建设,贸易做网站,人力资源管理师,百度推广售后服务电话G-子序列权值乘积 设计知识#xff1a; 欧拉降幂 如果我们要求ab%p 而b是一个很大的数#xff0c;可以先将b对p-1取模#xff0c;不会影响结果的正确性#xff0c;前提是a和p互质。
这一题我们可以将数字先进行排序#xff0c;因为子序列中只有最大和最小的才会被计算 欧拉降幂 如果我们要求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 用了欧拉降幂 // lr为左侧组合数加上右侧组合数加上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; }
