# Fragment sum of 1049 sequence (20 points) (c + +)

2022-01-27 04:30:36 ``````Notice:
1. Start by writing nested loops directly , Found timeout . So we need to use mathematical methods to solve .
Then refer to other people's blogs , Discover its regularity ：

First observe a number , for example , about N=4 The serial number in the sequence is 3 The fragment of the number of is as follows ：
( Starting from 1)[(1,2,3),(1,2,3,4)];
( Starting from 2)[(2,3),(2,3,4)];
( Starting from 3)[(3),(3,4)];
You can see it , Including i In the number of clips , The beginning of the fragment can be 1,2,3..i, altogether i A choice ,
( If included 3 The clips are 123 Three options )  The end of the clip can be i,i+1,...n, altogether n-i+1 A choice .
( If included 3 The clips are 34 Two options ).
So we can promote , For length is N The serial number in the sequence is i Number of numbers , The clip can be divided into i Parts of , The first i Part of the starting point is i,
The end points are i,i+1,i+2,...,N, common (N-i+1) individual , So sequence i The frequency of occurrence of is i*(N-i+1).
http://www.bubuko.com/infodetail-3010293.html

“N The larger the ,double Precision error caused by multiple accumulation of values of type , Because the input is decimal , Store in double In the middle of the day ,
Binary representation is used inside the computer , And the word length of the computer is limited , Some decimal floating point numbers cannot be accurately represented by binary
It's only infinitely close , Under the limitation of word length, rounding error is inevitable , These subtle errors are N When it is large, it is accumulated many times
There will be large errors , So it is recommended not to use double Type for accurate calculation of multiple accumulation , Instead, it can accurately store
The integer of . Try to input double The value of type is expanded 1000 Double and turn to long long Integer accumulation , Use at the same time
long long Type to save sum Value , Output divided by 1000.0 Convert to floating point type and then output （ It's equivalent to moving the decimal point back 3 Behind you
Calculate again , avoid double The decimal part of the type is stored imprecisely , After multiple accumulation, it will affect the results ）  But I think multiplied by 1000
Not necessarily rigorous , Maybe the test sample has at least three decimal places , If the test sample becomes four decimal places 、 Five place 、 Six ,
multiply 1000 It is equivalent to truncating directly at three decimal places , The original fourth, fifth and sixth digits may still cause
Precision problem , But if you multiply by 10000 It will go beyond long long Value , I think the most accurate is to intercept the largest of all decimals
The one with the number of digits .. Maybe there's something missing in my idea , After testing , The test sample does not exceed three decimal places ,
Although it is modified to multiply by 1000 The post code has AC, But if the test sample is slightly modified , It may lead to non AC 了 …
So put a question mark on this question first , I guess the sample title may be revised in the future …”
``````

my ( The code timed out )

``````#include <iostream>
#include <cstdio>
using namespace std;
int main(){

int n;
cin >> n;
float a[n];
for(int i = 0;i < n;i++){

cin >> a[i];
}
float sum1 = 0,sum2 = 0;
for(int i = 0;i < n;i++){

sum1 = 0;
for(int j = i;j < n;j++){

sum1 += a[j];
sum2 += sum1;
}
}
printf("%.2f",sum2);
return 0;
}
``````

Liunuo's code

``````#include <iostream>
using namespace std;
int main() {

int n;
cin >> n;
double temp;
long long sum = 0;
for(int i = 1;i <= n;i++){

cin >> temp;
sum += (long long)(temp * 1000) * i * (n - i + 1);
}
printf("%.2f",sum / 1000.0);
return 0;
}
``````