P10185 [YDOI R1] Necklace

[YDOI R1] Necklace - 洛谷

因为是方案数求和

我们考虑计算每种珠子单独贡献的方案数有

因为有二项式定理

构造

因为n不取0，便有

时间复杂度

modint + qmi code

#include <bits/stdc++.h>#define INF (1ll<<60)
#define eps 1e-6
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef vector<vector<int> > vii;
typedef vector<vector<vector<int> > > viii;
typedef vector<ll> vl;
typedef vector<vector<ll> > vll;
typedef vector<double> vd;
typedef vector<vector<double> > vdd;
#define time mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());//稳定随机卡牛魔 ull
const int mod=1e9+7;
template<class T>
constexpr T power(T a, LL b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}template<int P>
struct MInt {int x;constexpr MInt() : x{} {}constexpr MInt(LL x) : x{norm(x % getMod())} {}static int Mod;constexpr static int getMod() {if (P > 0) {return P;} else {return Mod;}}constexpr static void setMod(int Mod_) {Mod = Mod_;}constexpr int norm(int x) const {if (x < 0) {x += getMod();}if (x >= getMod()) {x -= getMod();}return x;}constexpr int val() const {return x;}explicit constexpr operator int() const {return x;}constexpr MInt operator-() const {MInt res;res.x = norm(getMod() - x);return res;}constexpr MInt inv() const {assert(x != 0);return power(*this, getMod() - 2);}constexpr MInt &operator*=(MInt rhs) & {x = 1LL * x * rhs.x % getMod();return *this;}constexpr MInt &operator+=(MInt rhs) & {x = norm(x + rhs.x);return *this;}constexpr MInt &operator-=(MInt rhs) & {x = norm(x - rhs.x);return *this;}constexpr MInt &operator/=(MInt rhs) & {return *this *= rhs.inv();}friend constexpr MInt operator*(MInt lhs, MInt rhs) {MInt res = lhs;res *= rhs;return res;}friend constexpr MInt operator+(MInt lhs, MInt rhs) {MInt res = lhs;res += rhs;return res;}friend constexpr MInt operator-(MInt lhs, MInt rhs) {MInt res = lhs;res -= rhs;return res;}friend constexpr MInt operator/(MInt lhs, MInt rhs) {MInt res = lhs;res /= rhs;return res;}friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {LL v;is >> v;a = MInt(v);return is;}friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {return os << a.val();}friend constexpr bool operator==(MInt lhs, MInt rhs) {return lhs.val() == rhs.val();}friend constexpr bool operator!=(MInt lhs, MInt rhs) {return lhs.val() != rhs.val();}
};template<>
int MInt<0>::Mod = 1e9 + 7;template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();constexpr int P = 1e9 + 7;
using Z = MInt<P>;const int N=2e5+9;Z inv[N],f[N],invf[N];//组合数
void init(){inv[1]=1;for(int i=2;i<N;i++){inv[i]=inv[mod%i]*(mod-mod/i);}f[0]=1,invf[0]=1;for(int i=1;i<N;i++){f[i]=f[i-1]*i;invf[i]=invf[i-1]*inv[i];}
}
Z C(ll n,ll m){if(n<m || m<0){return 0;}return f[n]*invf[m]*invf[n-m];
}
Z qmi(Z a,ll b){Z res=1;while(b){if(b&1){res=res*a;}b>>=1;a=a*a;}return res;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int n;cin>>n;vi a(n+1);ll sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}vi v(n+1);for(int i=1;i<=n;i++){cin>>v[i];}Z ans=0;for(int i=1;i<=n;i++){ans+=qmi(2,sum-a[i])*(qmi(v[i]+1,a[i])-1);}cout<<ans<<'\n';return 0;
}