题目

传送门

题目大意

给出$N(N\leq 10^5)$N(N≤105)个数围成一圈，每次你可以选择一个$i(1\leq i\leq N)$i(1≤i≤N)，然后对于每个$j(1\leq j\leq N)$j(1≤j≤N)，从第$i+j$i+j个数（循环计数）中减去$j$j（若其中的某个数会减成负数，你就不能选择这个$i$i），问最后是否可能使每个数都变成$0$0。

思路

原题的题意就是从一个数开始，顺时针方向第$i$i个数减去$i$i（相当于一个等差数列）。

首先，所有数之和$sum$sum必须是$1+2+...+N$1+2+...+N即$\dfrac{N(N+1)}{2}$2N(N+1)​的倍数。
然后，进行的操作数$k=\dfrac{sum}{1+2+...+N}$k=1+2+...+Nsum​。

假设选了数$a_i$ai​，那么除了$a_i$ai​和$a_{i+1}$ai+1​（都是循环计数），其他的每两个相邻的数之差都减小了$1$1。
例如：$6,9,12,10,8$6,9,12,10,8，从$6$6开始完成依一次这样的操作：

于是，除了$6$6和$9$9，其他的两个数之差都减小了$1$1，由于减去的是一个等差数列，所以不难理解这一点。
再看$a_i=6$ai​=6和$a_{i+1}=9$ai+1​=9之差，增加了$4$4，于是直接猜测：$a_i$ai​和$a_{i+1}$ai+1​的差会增加$N-1$N−1。
事实上就是这样的，可以很容易地推出来。

发现差值$d$d最多减少$k$k，所以先判断$d-k>0$d−k>0，若满足，任务不可能完成。
设进行了$x$x次“增加”的操作，则进行了$(k-x)$(k−x)次“减小”的操作，一定有：$d+x(N-1)-(k-x)=0$d+x(N−1)−(k−x)=0化简得：$k-d=xN$k−d=xN即$k-d$k−d必须是$N$N的倍数。

做完了，脑袋痛。

代码

#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;

#define MAXN 100000
int N;
int A[MAXN+5];

int main(){
    scanf("%d",&N);
    long long Sum=0;//注意long long
    for(int i=1;i<=N;i++){
        scanf("%d",&A[i]);
        Sum+=A[i];
    }
    long long All=1ll*N*(N+1)/2;
    if(Sum%All)
        return !puts("NO");
    int k=Sum/All;
    for(int i=1;i<=N;i++){
        int d=A[i]-A[i-1==0?N:i-1];
        if(d-k>0||(k-d)%N!=0)
            return !puts("NO");
    }
    puts("YES");
}