Responsive image

问题 G: 牢大的子序列权值和

问题 G: 牢大的子序列权值和

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 11
[提交][状态][讨论版][命题人:]

题目描述

牢大定义一个数组的权值为:数组所有元素乘积的因子数量。例如,[1,2,3]的权值为 4。
现在牢大拿到了一个数组,他想求出数组中所有非空子序列的权值之和。你能帮帮牢大吗?由于答案过大,请对109+7取模。
定义数组的子序列为:从左到右选择若干个元素(可以不连续)组成的数组,例如[1,2,3,2]的子序列有[2,2]等。因此,一个大小为nnn的数组有恰好2n-1个子序列。

输入描述

第一行输入一个正整数n,代表数组大小。
第二行输入n个正整数ai,代表数组的元素。  
1≤n≤1000 1≤ai≤3 (还行还行就三个数,感觉很ez啊

输出描述

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

样例输入

3
1 2 2

样例输出

15

提示

[1]的权值为 1。

[2]的权值为 2。

[2]的权值为 2。

[1,2]的权值为 2。

[1,2]的权值为 2。

[2,2]的权值为 3。

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

点我看什么是组合数,相信你一定用得到。

 

[提交][状态]
ACM算法攻关部
  • Anything about this OnlineJudge, Please Contact Administrator. Click add QQ

    OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap

    Copyright 2016 ACM算法攻关部
    关于网站改版