牛客周赛 Round 35 G.小红的子序列权值和（hard）【组合数+表达式等价转换】

时间：2024-03-08 17:35:54

原题链接：https://ac.nowcoder.com/acm/contest/76133/G

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

本题和easy版本的唯一区别是：n的数据范围不同！

小红定义一个数组的权值为：数组所有元素乘积的因子数量。例如，[1,2,3]的权值为 4。

现在小红拿到了一个数组，她想求出数组中所有非空子序列的权值之和。你能帮帮她吗？由于答案过大，请对10^9+7取模。
定义数组的子序列为：从左到右选择若干个元素（可以不连续）组成的数组，例如[1,2,3,2]的子序列有[2,2]等。因此，一个大小为n的数组有恰好2^n-1个子序列。

输入描述:

第一行输入一个正整数n，代表数组大小。
第二行输入n个正整数ai，代表数组的元素。
1≤n≤10^5
1≤ai≤3

输出描述:

一个整数，代表所有子序列的权值和。答案请对10^9+7取模。

示例1

输入

3
1 2 2

输出

15

说明

[1]的权值为 1。
[2]的权值为 2。
[2]的权值为 2。
[1,2]的权值为 2。
[1,2]的权值为 2。
[2,2]的权值为 3。
[1,2,2]的权值为 3。

解题思路：

简单数论题，现在我们有一个数组[1,2,2,2,3,3]，这个数字有一个子序列[2,2,3]，那么这个子序列的贡献是多少呢，这个子序列所有元素的乘积为v=2*2*3=2^2*3^1，根据基本的数论知识可以知道这个值的因子有(2+1)*(1+1)=6个，对于任意一个子序列所有元素的乘积都可以表示为若干质因子的乘积，例如v=p1^q1*p2^q2*.....pk^qk，那么此时的这个乘积的因子数为(q1+1)*(q2+1)*...*(qk+1)，然后还需要考虑1的出现次数，假设1总共有c1个，对于选中多少个1就会有temp=2^c1，对于所有的子序列的贡献就是C(s[2],i)*C(s[3,j)*temp*(i+1)*(j+1)，当n=1000时我们可以暴力的枚举2出现的次数i和3出现的次数j，但是这个题目n=1e5，所以我们肯定不能暴力枚举，但是我们上面已经分析出了计算的公式，我们可以看看有没有什么好的优化方式，上述计算公式可以转换为C(s[2],i)*(i+1)*C(s[3],j)*(j+1)*temp，实际上就是(a1+a2+...+ak)*(b1+b2+...+bk)*temp，根据分配律我们直接对俩个括号里面的值先预处理求和，然后再相乘和分解求和的答案是一样的，所以可以先分开预处理，然后再计算答案即可。

时间复杂度：O(n*log(n))，枚举2或者3出现的次数最坏是O(n),然后求逆元为log(n)

空间复杂度：O(n)。

cpp代码如下：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N=1e5+10,mod=1e9+7;
int n;
int s[4];
LL fact[N];

LL qmi(LL x,LL k)
{
    LL res=1;
    while(k){
        if(k&1)res=res*x%mod;
        k>>=1;
        x=x*x%mod;
    }
    return res;
}

LL inv(LL x){ //求逆元
    return qmi(x,mod-2);
}

LL C(int n,int m){ //求组合数
    return fact[n]*inv(fact[m])%mod*inv(fact[n-m])%mod;
}
int main()
{
    cin>>n;
    fact[0]=1;
    for(int i=1;i<=n;i++)fact[i]=(fact[i-1]*i)%mod; //预处理阶乘
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        s[x]++;
    }
    
    LL temp=1,c2=0,c3=0;
    for(int i=1;i<=s[1];i++)temp=temp*2%mod; //temp表示2^s[1]
    for(int i=0;i<=s[2];i++){  //处理好因子2那个括号里面的值
        c2+=C(s[2],i)*(i+1)%mod;
        c2%=mod;
    }
    for(int i=0;i<=s[3];i++){  //处理好因子3括号里面的那个值
        c3+=C(s[3],i)*(i+1)%mod;
        c3%=mod;
    }
    //计算答案，由于空序列也会被加1，或者最后还要减去1
    cout<<(c2*c3%mod*temp%mod-1+mod)%mod;
    return 0;
}

相关文章