前置芝士
- 二项式定理：\((a+b)^n=\sum \limits_{i=0}^{n}C^i_n\times a^i\times b^{n-i}\)
- 快速幂
Meaning
有 \(n\) 种珠子，每种有 \(a_i\) 颗，且美丽值为 \(v_i\)。任意两颗珠子不同（同种类也算不同）。每种珠子有一个漂亮值 \(v_i\)。项链有一个美丽度，若第 \(i\) 种珠子在项链中有 \(cnt\) 颗并且 \(cnt\ge1\)，则这串项链的美丽度会加上 \((v_i)^{cnt}\)。求所有不同的项链的美丽度总和是多少。
Solution
以下记 \(S=\sum\limits^n_{i=1} a_i\)，且以下式子默认对 \(10^9+7\) 取模。
subtask 1
留给搜索。
每一颗珠子枚举是否选择，即有 \(2^S\) 种项链。枚举一下就行。
时间复杂度 \(O(2^S)\)。
subtask 2
开始推式子。
对于第 \(i\) 种珠子，剩下 \(S-a_i\) 颗珠子，有 \(2^{S-a_i}\) 种取法。而在这 \(i\) 颗珠子中，取 \(x\) 颗，美丽值增加 \({(v_i)}^x\)。取 \(x\) 颗珠子的方案数为 \(C^x_{a_i}\)。所以答案为：
\[\begin{aligned}\sum \limits _{i=1}^n\sum\limits_{x=1}^{a_i}(2^{S-a_i}\times C^x_{a_i}\times {v_i}^x) &=\sum \limits _{i=1}^n[2^{S-a_i}\times \sum\limits_{x=1}^{a_i}(C^x_{a_i}\times {v_i}^x)] \end{aligned}\]时间复杂度 \(O(S\log S)\)。其中 \(\log S\) 是快速幂的时间复杂度。
subtask 3
显然，subtask 2 的时间复杂度会 T 飞。
外面一层明显无法化简，此时回头看一眼二项式定理：
\[(a+b)^n=\sum \limits_{i=0}^{n}C^i_n\times a^i\times b^{n-i} \]再看看里面那一坨式子：
\[\sum\limits_{x=1}^{a_i}(C^x_{a_i}\times {v_i}^x) \]稍微变下形：
\[\sum\limits_{x=1}^{a_i}(C^x_{a_i}\times {v_i}^x\times 1^{a_i-x}) \]这两个好像！
所以答案可以变为 \(\sum \limits _{i=1}^n[2^{S-a_i}\times (v_i+1)^{a_i}]\)？
由于原式中是从 \(1\) 开始遍历的，所以还需要减去 \(C_{a_i}^0\times {v_i}^0\times 1^{a_i}=1\)。
故答案为 \(\sum \limits _{i=1}^n\{2^{S-a_i}\times [(v_i+1)^{a_i}-1]\}\)
时间复杂度 \(O(n\log S)\)。
code
杜绝复制！
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[2000003],v[2000003];
int qpow(int a,int n,int mod)
{
int re=1;
while(n)
{
if(n&1)
re=(re*a)% mod;
n>>=1;
a=(a*a)%mod;
}
return re%mod;
}
signed main()
{
int n,ans=0,s=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
for(int i=1;i<=n;i++) cin>>v[i];
for(int i=1;i<=n;i++)
{
int cnt=0;
cnt=qpow(v[i]+1,a[i],1000000007)-1;
ans+=cnt*qpow(2,s-a[i],1000000007),ans%=1000000007;
}
cout<<ans;
return 0;
}