cho mình hỏi rằng khi tính P=(n-1)^2+(n-2)^2+…+1 mà mod cho 10^9+7 thì có cách nào mod ra kết quả nhanh ko chứ mình bỏ vào for vừa cộng vừa mod từng thành phần thì bị time limit, 3<=N<=10^3, ko biết có cách biến đổi P ra biểu thức rút gọn nào ko nhỉ??
Tính đa thức nhanh
Cái này tinh dễ mà. Kết quả chính bằng
2 Likes
e cũng biến đổi ra v rồi nhưng lúc nộp lại bảo sai nên mới đăng bài hỏi thử :((
Sai là sai thế nào, bạn up code lên đây xem.
2 Likes
#include<bits/stdc++.h>
typedef long long ll;
const ll h=pow(10,9)+7;
void thu(ll a[],ll n)
{
for(ll i=0;i<n;i++)
{
scanf("%lld",&a[i]);
}
}
void tinh(ll a[],ll n)
{
ll min,max;
for(ll i=0;i<n;i++)
{
ll k=(a[i]-1)/2;
min=((a[i]%h)*(k%h)*(k%h))%h;
max=(((a[i]%h)*((a[i]-1)%h)*((2*a[i]-1)%h))/6)%h;
printf("%lld %lld\n",min,max);
}
}
main()
{
ll a[100000];
ll n;
scanf("%lld",&n);
thu(a,n);
tinh(a,n);
}
đề v nè a, mà e thử số trên 10^7 là min lại ra âm :((
a*a*a là quá lớn rồi, mod không kịp đâu 
mỗi thừa số nhân vào là mod ngay.
p/s: Có thể chia path trước rồi mod để bench thử 
3 Likes
ý tưởng của mình hiện tại là do phải thử với nhiều bộ số nên dùng struct với 2 mảng min, max để tính luôn 1 lần từ 3->10^9, tính đến phần tử nào lưu đến phần tử nấy rồi khi nhập thì gặp N bằng bao nhiêu t sẽ lấy min, max tương ứng mà ko biết chạy đc ko???
Chia 6 sau khi nhân lấy mod như thế này không ổn tí nào. Kết quả chắc chắn sai.
2 Likes
hay là mình cứ làm theo ct tổng quát là 1^2+2^2+… cộng tới N nào lưu tới đó, khi nhập N thì đưa ra max, min tương ứng đã lưu trong mảng tính trước, do theo ct biến đổi thì min=n*((n-1)/2)^2 còn max thì như trên, tất cả đều dính đến n nên khi n chạy đến 10^9+7 thì =0 ???
n có chạy đến 10^9+7 đâu bạn, bạn nhìn lại giới hạn của n xem.
Để chia 6 được thì bạn thử xét tính chất chia hết qua số dư của n với 3, if else 1 tí là không cần phải mảng miếc gì cả, vẫn O(1) thôi.
2 Likes
Có công thức mà còn quýnh lên
Nhưng mà công thức min có lẽ ko đúng vì nếu n chẵn thì sẽ chia ra n/2 điểm và n/2-1 điểm.
3 Likes
à chỗ đó do chỉ là bt làm quen với modulo nên bộ test chỉ ứng với số chẵn thôi
à mà e đang học đến bài nghịch đảo modulo nên thay vì chia 6 mình nhân nghịch đảo của 6 được không a?
Tại sao phải lấy dao mổ trâu giết gà?
1 Like
Được nhé
Tức là hai nửa.
3 Likes
Mình không biết về thể thức thi đấu C1 như thế nào, có phải kiểu ví dụ có 3 đội A, B, C thì sẽ diễn ra các trận gồm A - B, A - C, B - C phải không ?
Nếu như đúng là như vậy thì công thức tính min của bạn sai rồi, với n = 4 thì min = 10 chứ, chứ không phải 9.
3 Likes
Gọi là vòng tròn 1 lượt chứ C1 đá vòng tròn 2 lượt rồi.
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?