VyUNs5 - Online C++0x Compiler & Debugging Tool

#include <bits/stdc++.h> // NeOWami
using namespace std;

#define ft first
#define sc second
#define int long long
using pii = pair<int, int>;
const int N = 1e5 + 5;
int n, b[N];
int a[N];

//a1 = (∑_(i=1..(n+2)/3) [b[pos(2 + (i - 1) * 3)]] - n * (n + 1) / 2);
inline int pos(int x) {
    x %= n;
    if (x == 0) x = n;
    return x;
}
namespace Type2 {
int calc(int posStart) {
    int ans = 0;
    for (int i = 1; i <= (n + 2) / 3; i++) ans += b[pos(posStart + (i - 1) * 3)];
    ans -= n * (n + 1) / 2;
    return ans;
}
void solve() {
    a[1] = calc(2 % n);
    a[2] = calc(3 % n);
    for (int i = 3; i <= n; i++) a[i] = b[i - 1] - a[i - 1] - a[i - 2];
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
}
};

//a1 = (∑_(i=1...(n*2+2)/3) [b[pos(2 + (i - 1) * 3)]] - n * (n + 1))
namespace Type1 {
int calc(int posStart) {
    int ans = 0;
    for (int i = 1; i <= (n * 2 + 2) / 3; i++) ans += b[pos(posStart + (i - 1) * 3)];
    ans -= n * (n + 1);
    return ans;
}
void solve() {
    a[1] = calc(2 % n);
    a[2] = calc(3 % n);
    for (int i = 3; i <= n; i++) a[i] = b[i - 1] - a[i - 1] - a[i - 2];
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
}
};

namespace Type0 {
int c[N], X[N], Y[N], Z[N], U, V, W, U2, V2, W2, m, P;
void init() {
    m = n / 3;
    P = n * (n + 1) * (2 * n + 1) / 6;
    for (int i = 1; i <= n; i++) c[i] = b[i] - b[pos(i - 1)];

    X[1] = U = U2 = 0;
    for (int i = 4; i <= n; i += 3) {
        X[i] = X[i - 3]  + c[i - 1];
        U += X[i];
        U2 += X[i] * X[i];
    }
    Y[2] = V = V2 = 0;
    for (int i = 5; i <= n; i += 3) {
        Y[i] = Y[i - 3]  + c[i - 1];
        V += Y[i];
        V2 += Y[i] * Y[i];
    }
    Z[3] = W = b[2];
    W2 = b[2] * b[2];
    for (int i = 6; i <= n; i += 3) {
        Z[i] = Z[i - 3]  + c[i - 1];
        W += Z[i];
        W2 += Z[i] * Z[i];
    }
}

pii PTB2(int a, int b, int c) {
    int delta = b * b - 4 * a * c;
    if (delta < 0) return {-1, -1};
    int sq = sqrtl(delta);
    int x1 = (-b - sq);
    if (x1 % (2 * a)) x1 = -1;
    else x1 /= (2 * a);

    int x2 = (-b + sq);
    if (x2 % (2 * a)) x2 = -1;
    else x2 /= (2 * a);

    if (x1 > x2) swap(x1, x2);
    return {x1, x2};
}

void getAns(int x, int y) {
    a[1] = x, a[2] = y;
    for (int i = 3; i <= n; i++) a[i] = b[i - 1] - a[i - 1] - a[i - 2];
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
}

void solve() {
    init();
    for (int x = 1; x <= n; x++) {
        int a = 2 * m;
        int b = 2 * m * x + 2 * V - 2 * W;
        int c = U2 + V2 + W2 + 2 * m * x * x + 2 * x * U - 2 * x * W - P;
        pii y = PTB2(a, b, c);
        // cerr << x << " " << y.ft << " " << y.sc << "\n";
        if (y.ft >= 1 && y.ft <= n && y.ft != x) return getAns(x, y.ft);
        if (y.sc >= 1 && y.sc <= n && y.sc != x) return getAns(x, y.sc);
    }
}
};

signed main() {
    cin.tie(NULL)->sync_with_stdio(false);
    if(ifstream("CIRCLE.inp")) {
        freopen("CIRCLE.inp", "r", stdin);
        freopen("CIRCLE.out", "w", stdout);
    }
    cin >> n;
    if (n == 1) return cout << 1, 0;

    for (int i = 1; i <= n; i++) cin >> b[i];
    if (n % 3 == 2) return Type2::solve(), 0;
    if (n % 3 == 1) return Type1::solve(), 0;
    return Type0::solve(), 0;
    return 0;
}

/*

if (n % 3 == 2)

1 2 3 4 5 6 7 8
a1 = (b2 + b5 + b8 - ∑_(i=1..8)[i]) / 2
or:
a1 = ∑_(i=2; i <= n; i += 3) [bi] - n * (n + 1) / 2
or a1 = ∑_(i=1..(n+2)/3) [b[pos(2 + (i - 1) * 3)]] - n * (n + 1) / 2;

if (n % 3 == 1)
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8 9 10
a1 = b2 + b5 + b1 + b4 + b7 - 2 * ∑_(i=1..8)[i]
or:
a1 = ∑_(i=1...(n*2+2)/3) [b[pos(2 + (i - 1) * 3)]] - n * (n + 1)


if (n % 3 == 0)
ý tưởng: giả sử cố định a1, có cách nào tìm a2 nhỏ nhát sao cho thỏa mãn hay không
(dễ dàng code trâu n ^ 3, giờ ta thử cải tiến nó lên để AC trường hợp n % 3 == 0)

vì n ≡ 0 (mod 3), ta thử chia ra thành các cụm ≡ 0, 1, 2 để xử lý và tính toán

dễ tính được b[i] - b[i - 1] = a[i + 1] - a[i - 2];
đặt c[i] = b[i] - b[i - 1];
a[i + 1] = a[i - 2] + c[i]
Hay a[i] = a[i - 3] + c[i - 1]            (1)
⇒ ta tìm ra được nhận định sau:
+Nếu có a[i] ta sẽ tính được a[i + 3]

Gọi X[i] là giá trị chênh lệch của a[i] cho a[1] với i ≡ 1 (mod 3);
    Y[i] là giá trị chênh lệch của a[i] cho a[2] với i ≡ 2 (mod 3);
    Z[i] là giá trị chênh lệch của a[i] cho a[3] - b[2] với i ≡ 0 (mod 3) (xem ở dưới để hiểu lý do);

Đặt:
a[1] = x
a[2] = y
dễ thấy:
nếu i ≡ 1 (mod 3): a[i] = x + X[i];
nếu i ≡ 2 (mod 3): a[i] = y + Y[i];
nếu i ≡ 0 (mod 3): a[i] = (- x - y) + Z[i];
với:
X[1] = 0, với i = 4,7,.. X[i] = X[i - 3] + c[i - 1]  (c/m từ (1))
Y[2] = 0, với i = 5,8,.. Y[i] = Y[i - 3] + c[i - 1]  (...)
Z[3] = b[2], với i = 6,9,.. Z[i] = Z[i - 3] + c[i - 1] (... và vì b[2] = a[1] + a[2] + a[2] ⇒ a[3] = b[2] - x - y)

Bằng cách biến đổi này, ngoài x và y, tất cả các giá trị còn lại đều là hằng số và có thể tính được
Do đó ta tìm cách giải y khi có x
Đặt m = n / 3

Tới đây nếu cố tình bằng cách giải thay vào ∑_(i=1..n) [a[i]] = n * (n + 1) / 2 thì chắc chắn sẽ không ra (*)
(có thể tự làm thử để hiểu vì sao =))) )

*Ta chuyển sang sài: ∑_{i=1..n} a[i] ^ 2
Ký hiệu:
U = ∑_{i=1..n} X[i];  U2 = ∑_{i=1..n} X[i]^2;
V = ∑_{i=1..n} Y[i];  V2 = ∑_{i=1..n} Y[i]^2;
W = ∑_{i=1..n} Z[i];  W2 = ∑_{i=1..n} Z[i]^2;

Khai triển: ∑_{i=1..n} a[i] ^ 2
= ∑_{i=1,4,..} (x+X[i])^2 + ∑_{i=2,5,..} (y+Y[i])^2 + ∑_{i=3,6,..} (-x-y+W[i])^2
= m*x^2 + 2*x*U + U2 + m*y^2 + 2*y*V + V2 + m*x^2 + m*y^2 + W2 + m*2*x*y -2*x*W -2*y*W
= 2m*y^2 + (2m*x+ 2*V - 2*W)y + (U2 + V2 + W2 + 2*m*x^2 + 2*x*U -2*x*W)
Mà ta có: ∑_{i=1..n} a[i] ^ 2 = n*(n+1)*(2n+1)/6 ( = P)
⇔ 2m*y^2 + (2m*x + 2*V - 2*W)y + (U2 + V2 + W2 + 2*m*x^2 + 2*x*U -2*x*W - P) = 0
Tới đây khi thay x, ta có thể giải y như giải PT bậc 2

Vậy ta có thể giải bài này với O(n)

P/S:
lý do phải chia trường hợp liên quan trực tiếp tới (*)
∑_{i=1..n} (a[i]) = n * (n + 1) / 2 (I)
⇔ n0*x + U + n1*y + V - n2*(x + y) + W = n * (n + 1) / 2;

Nếu n % 3 == 0:
ta được n0 = n1 = n2 = m, do đó triệt tiêu hết x, y
Từ đó sẽ luôn ra phương trình PT (I) luôn đúng với mọi x, y
Do đó ta chỉ cần giải phương trình ∑_{i=1..n} a[i] ^ 2 = P

Còn với n % 3 != 0, ta chuyển sang giải bài toán hệ phương trình:
+ ∑_{i=1..n} (a[i]) = n * (n + 1) / 2
+ ∑_{i=1..n} (a[i] ^ 2) = P
Tới đây sài cách cũ vẫn code ngắn và tốt hơn nhiều

*/