题目概述

有一个序列 $\{a_n\}$ ，令 $\{b_i=a_i\ mod\ a_{i\ mod\ n+1}\}$ ，现在给出 $\{b_n\}$ ，求出一组可行的 $\{a_n\}$ 。

解题报告

构造题什么的根本不会，我来抄题解。

考虑 $\forall i<n-1,a_i-a_{i+1}=b_i,2a_{i+1}>a_i$ 以及 $a_n=b_n,a_1>a_n$ ，这样一定是一组合法解。

我们让 $a_i=\sum_{j=i}^{n-1}b_j+x$ ，然后让 $x$ 尽量大就能满足前面的条件，但 $x$ 必须是 $b_n$ 的倍数，所以我们可以找一个最大的 $a_{max}$ ，把 $max$ 循环推到 $n$ ，然后 $a_i=\sum_{j=i}^{n-1}b_j+b_n$ 。

这样基本上是满足 $a_1>a_n$ 的情况的，除了 $\{b_n\}$ 只有一个非 $0$ 其他全是 $0$ 的情况，这样就不满足了，需要特殊处理。或者不特殊处理，直接 $a_i=\sum_{j=i}^{n-1}b_j+kb_n,k>1$ 就行了。

但是什么时候不存在解？如果 $\{b_n\}$ 全一样但不是 $0$ ，就无解了（很明显这样无法按照上面的方法构造）。yy一下发现挺显然的：要么 $a_i<a_{i+1},a_i=b$ 要么 $a_i-ka_{i+1}=b$ 。全是第一种是不可能的；如果不存在前面这种那么 $a_n$ 不是 $b$ 而且 $a_1>a_n$ 所以不满足；如果两种都存在那么将会从一个地方开始变为全是第二种，所以也不满足。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=140582;

int n,b[maxn+5],c[maxn+5],MAX;LL a[maxn+5];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&c[i]),MAX=max(MAX,c[i]);
    int pos=0;c[0]=c[n];for (int i=1;i<=n;i++) if (c[i-1]<MAX&&c[i]==MAX) {pos=i;break;}
    if (!pos){
        if (!MAX) {puts("YES");for (int i=1;i<n;i++) putchar('1'),putchar(' ');puts("1");}
        else puts("NO");return 0;
    }
    for (int i=pos,j=n;i;i--,j--) b[j]=c[i];for (int i=pos+1,j=1;i<=n;i++,j++) b[j]=c[i];
    puts("YES");a[n]=b[n];a[n-1]=b[n-1]+(b[n]<<1);for (int i=n-2;i;i--) a[i]=a[i+1]+b[i];
    for (int i=n-pos+1;i!=n-pos%n;i<n?i++:i=1) printf("%lld ",a[i]);printf("%lld\n",a[n-pos%n]);return 0;
}