题解：CF1618E Singers' Tour

· · 题解

推式子 + 求解线性方程组

根据题意，由于\{b\} 序列共有 n 项且对于每个 b_i 都可以用含 a_{1 \sim n} 的式子来表示，即有 n 个线性方程以及 n 个未知量 a_{1 \sim n}，显然容易想到联立线性方程求解。

对于这种问题我们应该如何考虑呢？首先光瞪眼肯定是不行的，你需要列出来看看规律。为了避免被绕晕，你需要列出 n 行先，然后依次对 i \in [1,2,\cdots,n] 进行考虑，把 a_i 对应在每一行产生的贡献加进去（从第 i 行权值为 1 开始进行依次考虑这样可以很方便地表示出来，就不会乱），注意每一个 b_i 对应的所有 a 的表示要对齐即可，这样方便观察数量的性质以及便于进行计算。当然我们可以不需要把 n 行都具体地列出来，比如我们可以只列出前两行和最后一行，已经足够我们观察了。

列出方程组如下：

\begin{cases} b_1=a_1+na_2+(n-1)a_3+\cdots+2a_n \\ b_2=2a_1+a_2+na_3+\cdots+3a_n \\ \vdots \\ b_n=na_1+(n-1)a_2+(n-2)a_3+\cdots+a_n \end{cases}

不能考虑高斯消元求解线性方程组，因为高斯消元法时间复杂度为 O(n^3) 会 TLE，考虑观察法解方程组。

观察不难发现：

b_{i}-b_{i-1}=\sum_{k=1}^na_k- n \cdot a_i

即：

a_i =\dfrac{\sum_{k=1}^na_k - (b_i-b_{i-1})}{n}

显然我们只要知道 \sum_{k=1}^na_k 的值，我们就可以解出每一个 a_i，于是接下来我们的任务就是求解 \sum_{k=1}^na_k 的值。

观察线性方程组不难发现，对这个线性方程组左右部分相加可得：

\sum_{i=1}^nb_i = \sum_{i=1}^n \Bigg(\sum_{j=1}^nj \times a_i \Bigg)

和式变换交换求和次序即：

\sum_{i=1}^nb_i = \Bigg(\sum_{j=1}^n j \Bigg) \times \Bigg(\sum_{i=1}^n a_i \Bigg)

考虑等差数列求和公式化简，即：

\sum_{i=1}^nb_i =\dfrac{n(1+n)}{2} \times \sum_{i=1}^n a_i

故：

\sum_{i=1}^n a_i = \sum_{i=1}^nb_i \times \dfrac{2}{n(1+n)}

于是 \sum_{k=1}^na_k 也求解出来了。

回顾思路：先计算出 \sum_{k=1}^n a_k，然后依次枚举 i \in [1,n]，看一下是否都满足 a_i =\dfrac{\sum_{k=1}^na_k - (b_i-b_{i-1})}{n} 可被整除且为整数，只要存在一项不满足则无解。

然后你会发现，要计算 a_i 时需要用到 b_i 和 b_{i-1}，那么对于 a_1 该如何计算呢？观察一开始的线性方程组你会发现，满足 a_1 =\dfrac{\sum_{k=1}^na_k - (b_1-b_{n})}{n}，你可以单独对 a_1 进行处理，也可以就在循环中用一个 lst 变量来灵活处理，可见代码。

此外，对于无解的判定还有以下两个细节：

typedef long long LL;
const int N=4e4+5;
int n;
int a[N],b[N];
void solve(){
    cin>>n;
    rep(i,1,n) cin>>b[i];
    LL S=0;
    rep(i,1,n) S+=b[i];
    if(S*2%(n*(n+1))!=0) return cout<<"NO",void();
    S=S*2/(n*(n+1));
    rep(i,1,n){
        int lst=(i-1)%n;
        if(!lst) lst=n;
        LL x=S-(b[i]-b[lst]);
        if(x%n!=0 || x/n<=0) return cout<<"NO",void();
        a[i]=x/n;
    }
    cout<<"YES"<<endl;
    rep(i,1,n) cout<<a[i]<<" ";
}