[YDOI R1] Necklace 题解

· · 题解

或许更好的阅读体验/题目传送门

前置芝士

  1. 二项式定理：(a+b)^n=\sum \limits_{i=0}^{n}C^i_n\times a^i\times b^{n-i}
  2. 快速幂

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;
}