【每日一题】7月21日题目精讲—区间权值

$\color{#FFA000}{【暑假特别计划】}$
活动时间：7月7日起至9月1日
活动内容：写当日题解，活动时间内一共写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

$\color{#FFD700}{【特别介绍】}$
每日一题交流群，群内定期有福利发放，群号：659028468

今日每日一题预告
题号 NC19798
名称区间权值
来源牛客国庆集训派对Day4
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

如果你会直接和式变换，那么直接化简就可以了~~
如果数学不是那么好，我们可以考虑展开然后观察：
展开之后发现答案应该是
f(1,1)+f(1,2)+f(1,3)+...+f(1,n)
+f(2,2)+f(2,3)+...+f(2,n)
+f(3,3)+...+f(3,n)
………………
+f(n,n)
然后再继续拆开 $a_1w_1+(a1+a_2)w_2+(a_1+a_2+a_3)w_3+...+(a_1+a_2+a_3+...+a_n)w_n$
$+a_2w_2+(a_2+a_3)w_3+...+(a_2+a_3+...+a_n)w_n$
……
这样表示不太方便，我们用sum[i]表示a数组前缀和，那么： $(sum[1]-sum[0])w_1+(sum[2]-sum[0])w_2+...+(sum[n-2]-sum[0])w_(n-2)+(sum[n-1]-sum[0])w_(n-1)+(sum[n]-sum[0])w_n$
$+(sum[2]-sum[1])w_1+(sum[3]-sum[1])w_2+...+(sum[n-2]-sum[1])w_(n-2)+(sum[n]-sum[1])w_(n-1)$
$+(sum[3]-sum[2])w_1+(sum[4]-sum[2])w_2+...+(sum[n]-sum[2])w_(n-2)$
………… $+(sum[n]-sum[n-1])w_1$
然后将 $w_i$ 的系数合并： $w_1$ 的系数： $sum[1]-sum[0]+sum[2]-sum[1]+sum[3]-sum[2]+....+sum[n]-sum[n-1]$ ，为 $sum[n]-sum[0]$
$w_2$ 的系数： $sum[2]-sum[0]+sum[3]-sum[1]+sum[4]-sum[2]+....+sum[n]-sum[n-2]$ ，为 $sum[n]+sum[n-1]-sum[1]-sum[0]$
$w_3$ 的系数： $sum[n]+sum[n-1]+sum[n-3]-sum[2]-sum[1]-sum[0]$
…… $w_n$ 的系数： $sum[n]-sum[0]$ ，我们可以把它当作 $sum[n]+sum[n-1]+sum[n-2]+...+sum[1]-sum[n-1]-sum[n-2]-...-sum[1]-sum[0]$
即w_i的系数是sum[i]的后i项和减去前i项和
于是我们对sum[i]再求一个前缀和sum[i]，于是 $w_i$ 的系数为summ[n]-summ[n-i]-sum[i-1]