G 子序列权值乘积

G 子序列权值乘积

#includeusing namespace std;#define rep(i,l,r) for(int i=(l);i<=(r);i++)#define per(i,l,r) for(int i=(l);i>=(r);i--)#define ll long long#define pii pair#define mset(s,t) memset(s,t,sizeof(t))#define mcpy(s,t) memcpy(s,t,sizeof(t))#define fir first#define pb push_back#define sec second#define sortall(x) sort((x).begin(),(x).end())inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= (ch=='-'),ch= getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x;}template void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0');}const int N = 2e5 + 10;const int mod = 1e9 + 7;ll qmi (ll a, ll b, ll mod) { ll ans = 1; while(b) { if (b & 1) ans = ans * a % mod; b >>= 1; a = a * a % mod; } return ans;}ll inv (ll a, ll mod) { return qmi(a, mod - 2, mod) %mod;}int n;ll a[N];void solve() { cin >> n; ll res= 1, tmp = 1; rep(i, 0, n - 1) { cin >> a[i]; res = res * a[i] %mod; tmp = tmp * a[i] %mod * a[i] %mod; } sort(a, a + n); int l = 0, r = n - 1; while (l < n -1) { tmp = tmp * inv(a[l ++], mod ) %mod * inv(a[r --], mod) %mod; res = res* qmi(tmp %mod, qmi(2, l - 1, mod - 1), mod) %mod %mod; } //枚举2-n for (int i = 0; i < n; i ++) res = res * a[i] %mod;//长度为1 cout << res << endl;}int main () { int t; t = 1; while (t --) solve(); return 0;}

由于总共有2^n - 1种子序列，直接枚举肯定不行 因为我我们只关心最大值和最小值，我们排序后，可以观察到固定最大值和最小值的时候，以及长度我们的贡献就确定了。 但是我们还需要接着优化？我们通过尝试枚举长度为1，为2，为3的例子，可以发现一种枚举的规律. 但是我们还要解决幂指数过大的情况可以通过欧拉降幂，对于a^b %p如果a和p互质那么我们通过费马小定理，a^(p - 1) %p = 1 将b表示成(p - 1) * u + v然后原来的式子，a^(p - 1)*u * a^v前者为1，因此可以得到更小的指数且不影响结果 这一题通过观察排序后的结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。