E. Singers’ Tour

题目描述：

给你一个b数组，需要构造一个a数组，可以理解为一个环，a数组产生b数组的方法是，a[i]在他后面的每一个位置的j产生的价值是a[i] * (j - i + 1),因为是个环，所以n+1的位置是1…

比如

b: 12 16 14
a: 3 1 3
a[1]产生的影响  3 6 9
a[2]产生的影响  3 1 2
a[3]产生的影响  6 9 3
求和后         12 16 14

思路

思维 + 构造

显然a[i]对整个b数组产生的价值是a[i] + a[i] * 2 + ...a[i]*n,也就是a[i] * (n + 1)*n/2

所以\sum{b[i]} = {n*(n+1)/2}*\sum{a[i] }

这是一个最基础的判NO的点

再就是怎么构造？

可以发现这其实是一个n个n元一次方程，仅有一解！

那怎么搞？高斯消元？大可不必

我们可以写一个邻项做差的式子：

拿三个数来说

b[1] = a[1] + 3 * a[2] + 2 * a[3]

b[2] = 2 * a[1] + a[2] + 3 * a[3]

做差得到：

b[1]-b[2] = -a[1] + 2 * a[2] - a[3]

移向：

2 * a[2] = b[1] - b[2] + a[1] + a[3]

两边同时加上a[2]

得到：

3 * a[2] = b[1] - b[2] + a[1] + a[2] + a[3]

也就是说：a[i % n + 1] = (b[i] - b[i % n + 1] + sum) / n，其中 sum = \sum{a[i]} = \frac{\sum{b[i]}}{\frac{(n+1)*n}{2}}

如果算出来的a[i]<1 || a[i]>1e9则输出NO

如果sum < n也输出NO

ll n, m, k, op;
int x, y, z;
ll a, b, c;
string s, t;
ll tr[MAX];
ll ans[MAX];

void work(){
    cin >> n;
    ll sum = 0;
    rep(i, 1, n){
        cin >> tr[i];
        sum += tr[i];
    }
    m = (n + n * n) / 2;
    if(sum % m ||  sum / m < n){
        cout << "NO\n";
        return;
    }
    else {
        m = sum / m;
        for(int i = 1; i <= n; ++i){
            ans[i % n + 1] = (m + tr[i] - tr[(i % n) + 1]) / n;
            if((m + tr[i] - tr[(i % n) + 1]) % n || ans[i % n + 1] > 1000000000 || ans[i % n + 1] < 1){
                cout << "NO\n";
                return;
            }
        }
        cout << "YES\n";
        rep(i, 1, n)cout << ans[i] << ' ';
        cout << endl;
    }
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
    //    printf("Case #%d: ", _t);
        work();
    }
    return 0;
}