Nice Trick

The input contains zero or more test cases and is terminated by end-of-file. For each test case,
The first line contains an integer n.
The second line contains n integers $a_1, a_2, \dots, a_n$ .

* $1 \leq n \leq 10^5$
* $0 \leq a_i \leq 10^9$
* The number of tests cases does not exceed 10.

C++14(g++5.4) 解法, 执行用时: 578ms, 内存消耗: 10116K, 提交时间: 2019-10-05 20:51:29

#include<iostream>
using namespace std;
int main(){
   long long n, a, s[5];
   while(cin >> n){
        s[0] = 1;
        s[1] = s[2] = s[3] = s[4] = 0;
      for(int i = 1; i <= n; i++){
            cin >> a;
         for(int j = 4; j > 0; j--){
            s[j] = (s[j] + s[j-1]* a) % 1000000007;
        }
      }
      cout << s[4] << endl;
   }
    return 0; 
}

C++11(clang++ 3.9) 解法, 执行用时: 547ms, 内存消耗: 496K, 提交时间: 2020-02-25 21:20:56

#include<iostream>
using namespace std;
int main()
{
	long long n,a,s[5];
	while(cin>>n)
	{
		s[0]=1;
		s[1]=s[2]=s[3]=s[4]=0;
		for(int i=1;i<=n;i++)
		{
			cin>>a;
			for(int j=4;j>0;j--)
			s[j]=(s[j]+s[j-1]*a)%1000000007;
		}
		cout<<s[4]<<endl;
	}
	return 0;
}

详情