橙子建站链接_汕头市网络推广平台_最新中国新闻_网络网站推广优化

题目链接

https://www.luogu.com.cn/problem/P10185

前置知识

• 二项式定理：$(a+b{)}^n={\sum }_{i=0}^n{C}_n^i\times a^i\times b^{n-i}$
• 组合数学
• 快速幂

思路

令$sum={\sum }_{i=1}^n{a}_i$。

我们从$1$到$n$枚举每一种珠子。

我们令$cnt$表示除第$i$种珠子以外所有珠子的选取方案数，则$cnt=2^{sum-a_i}$。

令$S$表示只选取第$i$种珠子时对答案产生的贡献。根据二项式定理，易推得$S=(v_i+1{)}^{a_i}-C_{a_i}^0\times v_i^0$。

第$i$种珠子对答案的总贡献为$=S\times cnt$。

统计所有珠子对答案的贡献之和即可。

时间复杂度：$O(nlogn)$。

代码

#include <bits/stdc++.h>using namespace std;#define int long long
#define double long doubletypedef long long i64;
typedef unsigned long long u64;
typedef pair<int, int> pii;const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;std::mt19937 rnd(time(0));int n;
int a[N], v[N];
int power(int a, int b, int c)
{int res = 1;while (b){if (b & 1) res = res * a % c;b >>= 1;a = a * a % c;}return res;
}
int MOD(int x)
{return (x % mod + mod) % mod;
}
void solve(int test_case)
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> v[i];}int sum = 0;for (int i = 1; i <= n; i++){sum = sum + a[i];}int ans = 0;for (int i = 1; i <= n; i++){int cnt = power(2, sum - a[i], mod);int S = (power(v[i] + 1, a[i], mod) - 1) % mod;ans = ans + S * cnt % mod;ans %= mod;}cout << MOD(ans) << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve(i);}return 0;
}