[CF2195D] Absolute Cinema 题解
题目传送门
写这道题的题解没啥必要，主要是为了锻炼下自己敲 \(\LaTeX\) 公式的能力。
题目大意
有一个你未知的数列 \(a_1,a_2,\ldots,a_n\) ，保证 \(|a_i| \le 1000\) 和 \(n \ge 2\) .
定义函数 \(f(n)\) 如下：
\(f(x)=\sum_{i=1}^n a_i \cdot |i-x|\)
给你 \(f(1),f(2),\ldots,f(n)\) 的值，让你反推整个数列 \(a\) 。
分析
那还说啥了都考我数学了直接推式子就完了呗。
感觉这种形式的式子看着就很适合差分地做啊。
\(f(x)-f(x-1)=\sum_{i=1}^n a_i \cdot( |i-x| - |i-x+1|)\)
发现\(|i-x| - |i-x+1|=\begin{cases} 1，i\le x\\-1，i\ge x\end{cases}\)
综合一下，\(f(x)-f(x-1)=\sum_{i=1}^{x-1} a_i - \sum_{i=x}^{n} a_i\)
然后再二阶差分一下，发现 \((f(x+1)-f(x))-(f(x)-f(x-1))=2a_x\)
然后就做出来了。
需要注意的是上面的式子由于边界问题，对于 \(x=1\) 或 \(x=n\) 不成立，暴力计算一下就好。
参考代码
数学题，所以代码并不复杂。
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=300010;
int n;
ll a[N],f[N];
void work(){ll sum1=0,sum2=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld",&f[i]);}for(int i=2;i<n;i++){a[i]=f[i+1]+f[i-1]-(f[i]<<1);a[i]>>=1;sum1+=a[i]*(i-1);sum2+=a[i]*(n-i);}a[1]=(f[n]-sum2)/(n-1);a[n]=(f[1]-sum1)/(n-1);for(int i=1;i<=n;i++){printf("%lld ",a[i]);}printf("\n");
}
int main(){int t=1;scanf("%d",&t);while(t--)work();
}