欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CF101532J The Hell Boy(暴力模拟)

程序员文章站 2022-03-11 21:06:11
...

题面:

Since the problem set was hard, here is an easy task for you to solve.

You are given an array a consisting of n integers, and your task is to calculate the summation of the multiplication of all subsets of array a. (See the note for more clarifications)

A subset of an array a is defined as a set of elements that can be obtained by deleting zero or more elements from the original array a.

 

Input:

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 105), where n is the size of array a.

The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.

 

Output:

For each test case, print a single line containing the summation of the multiplication of all subsets of array a. Since this number may be too large, print the answer modulo 109 + 7.

 

Example:

CF101532J The Hell Boy(暴力模拟)

 

Note:

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

In the first test case, the array a has 6 subsets, and the answer is calculated as follow:

(1) + (2) + (3) + (1 × 2) + (1 × 3) + (2 × 3) + (1 × 2 × 3) = 23

 

分析:

这道题其实我也没有把内涵想得很清楚,大概是个提公因式找规律的题,sum[i] = sum[i-1] * num[i] + num[i] + sum[i-1] 核心就在这个规律递推式上。

1: 1 = 1

2: 2 + 1*2 + 1 = 5

3: 3 + (1 + 2 + 1*2)*3 + 5 = 23

 

AC代码:

#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
const int maxn = 100010;
int t, n, num[maxn];
ll mod = 1E9+7;
ll sum[maxn];

int main(){
	cin>>t;
	while(t--){
		cin>>n;
		for(int i = 0; i < n; i++) scanf("%d", &num[i]);
		sum[0] = num[0];
		for(int i = 1; i < n; i++){
			sum[i] = (sum[i-1] + num[i] + sum[i-1] * num[i]) % mod;
		}
		printf("%lld\n", sum[n-1] % mod);
	}
	return 0;
}