mn cho e xin cách tối ưu bài toán này được không ạ, code của e submit thì bị báo timelimit ạ
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100001];
int main()
{
do{
cin>>n;
}
while(n>1E5||n<2);
int i=0,j;
for(int i=0;i<n;i++)
do{
cin>>a[i];
}
while(a[i]>1000||a[i]<1);
int s=0;
while(i<n){
for(j=i+1;j<n;j++)
s=s+a[i]*a[j];
i++;
}
cout<<s;
return 0;
}
Bài tương tự, khó hơn xíu và ít toán hơn 
đây em :V :V
cái này là toán thôi :V
#include <iostream>
int main()
{
long long n, s1 = 0, s2 = 0;
for (std::cin >> n; std::cin >> n;) s1 += n, s2 += n * n;
std::cout << (s1 * s1 - s2) / 2 << "\n";
}
vì (x1 + x2 + x3 + … + xn)2 = x12 + x22 + x32 + … + xn2 + 2(x1x2 + x1x3 + … xn-1xn) = x12 + x22 + x32 + … + xn2 + 2S
vậy S = [(x1 + x2 + x3 + xn)2 - (x12 + x22 + x32 + … + xn2)] / 2
cái công thức này giống (a+b+c)2 = a2 + b2 + c2 + 2(ab + bc + ca) ấy :V Nếu thêm d, e, f, … vào thì nó cũng ra như vậy :V
s1 là tổng các số hạng
s2 là tổng bình phương các số hạng
s1, s2 có kiểu long long để khỏi tràn số :V
đáp án là (s1*s1 - s2) / 2
khỏi cần mảng gì hết đọc vào cộng dồn luôn :V
e cám ơn nhiều ạ 
Gs k \ (sum(a[1..k]))^2 = sum(a[1..k]^2) + 2*sigma(m<n && m,n = 1..k)(a[m]a[n])
Vậy (sum(a[1..k+1]))^2 = (sum(a[1..k]))^2 + 2*sum(a[1..k])*a[k+1] + a[k+1]^2
(hằng đẳng thức)
= sum(a[1..k+1]^2) + 2*sigma(m<n && m,n = 1..k+1)(a[m]a[n]) (gom a[k+1] vào sigma)đã sửa lại với html sup sub :V :V
tại input có số lượng số hạng n nên nếu xài while phải thêm 1 cái cin >> n ở ngoài, thôi xài for bỏ vô trong cho tiết kiệm :V :V Đáng lẽ phải thêm 1 biến x nữa để phân biệt với n nhưng vì n ko xài nữa nên gộp chung thành code đểu luôn :V
giả sử nếu mình ko biết tới công thức toán trên thì có cách nào để giải mà tối ưu nữa không ạ
Thì gấp đôi lên đặt nhân tử chung mình cũng có nhớ hằng đẳng thức n số đâu.
Một cách giải khác: ta biết (sigma(a))^2 = sigma(a, a’)(aa’) (tính phân phối)
Ta trừ đi phần trùng là sigma(a^2), do tính giao hoán nên chia đôi.
Cách ở lầu trên trong for sẽ là
// C++11
uint64_t sum = 0, sumsq = 0;
for(auto v: numbers) {
sum += v;
sumsq += v*v;
}
Của bạn là
uint64_t sum = 0, sumsq = 0;
for(int i=1; i<numbers.length; ++i) {
sum += numbers[i-1];
sumsq += sum*numbers[i];
}
Cách trên sẽ nhanh hơn 
nhưng lại không tổng quát Nếu ko để ý cận thì khó mà nghĩ ra được cách đặt nhân tử chung đó.
thật ra ban đầu anh cũng mò thôi em ạ. đâu có nhớ công thức kia :V
bắt đầu với b0 nhân với n-1 các bj còn lại (j > 0)
tới b1 phải nhân với n-2 các bj còn lại (j > 1)
tới đây thì anh nhận thấy :V tích của bi với bk (k bất kì) = tích của bi và tổng S1 = b0 + b1 + … + bn-1. Vậy thay vì tính nhiều tích n-1, n-2, n-3, … ta chỉ cần tính 1 phép nhân cho mỗi tích là đủ: biS1. Nhưng bi nó ko bắt cặp với chính nó được nên ta cần trừ bi2 nữa. Và vì đề yêu cầu tích của bi và bj với i < j, tích biS1 - bi2 bao gồm cả i > j, nhưng may mắn là bibj = bjbi :V nên chỉ cần chia 2 thêm là xong.
vậy anh tìm ra được công thức tính nhanh là tổng (biS1 - bi2) rồi chia 2.
tới đây thì đã là O(n) rồi: tìm S1 là tổng mảng O(n), loop thêm 1 vòng for cho bi O(n) nữa là xong. Nhưng anh thấy ta còn có thể làm tốt hơn nữa :V Tổng biS1 vì nhân với S1 nhiều lần mà S1 là hằng số, ta có thể rút ra ngoài, công thức còn lại là S1(b0 + b1 + … + bn-1) = S12. Vậy nếu ta đặt S2 = b02 + b12 + … + bn-12 (tổng bình phương) thì ta có công thức cuối cùng là S = (S12 - S2) / 2
sau đó để cho chắc ăn là công thức đúng, anh gu gồ thì ra trang này :V :V https://www.geeksforgeeks.org/sum-product-pairs-array-elements/ nó giải thích bằng công thức toán kia :V :V :V nên anh thấy mình hơi ngu =]] nên chém gió bằng công thức toán này cho người ta tưởng mình giỏi toán =]]
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?