NC 19798区間重み値

題意:長さn n nのシーケンスa aとw w wを与えて、Σl=1 nΣr=l n f(l,r)sum_を求める{l=1}^{n}\sum_{r=l}^{n}f(l,r)Σl=1 nΣr=lnf(l,r)でf(l,r)=(Σi=lr a i)× w r − l + 1 f(l,r)=(\sum_{i=l}^{r}a_i)\times w_{r-l+1} f(l,r)=(∑i=lr​ai​)×wr−l+1,答えは1 0 9+7 10^9+7 109+7に対して型をとる.データ範囲:1≦n≦3× 1 0 5 , 1 ≤ a i ≤ 1 0 7 , 1 ≤ w i ≤ 1 0 7 1\leq n\leq 3\times10^5,1\leq a_i\leq 10^7, 1\leq w_i\leq 10^7 1≤n≤3×105,1≤ai​≤107,1≤wi​≤107
問題解:Σi=l r a isum_を先に計算する{i=l}^{r}a_i ∑i=lr​ai​

まず、長さが1 1 1のa[1,1]+a[2,2]+を考慮する.a [ n , n ] = a [ 1 , n ] a[1,1]+a[2,2]+...+a[n,n]=a[1,n] a[1,1]+a[2,2]+...+a[n,n]=a[1,n]

は、長いが2 2のa[1,2]+a[2,3]+a[3,4]+を引き続き考慮する.a [ n − 3 , n − 1 ] + a [ n − 2 , n ] a[1,2]+a[2,3]+a[3,4]+...a[n-3,n-1]+a[n-2,n] a[1,2]+a[2,3]+a[3,4]+...a[n−3,n−1]+a[n−2,n]は,第1項のa[1,2]a[1,2]a[1,2]の1,2,2,2,2,2,2,2,第2項のa[2,3]a[2,3]a[2,3]a[2,3]の3 3,3をとることを考慮し,...これにより,最後項までa[n−2,n]a[n−2,n]a[n−2,n]a[n−2,n]のn n n n nをとる.第2項から各項の第1元素が多くなると2,3,4,.,n − 1 , n 2,3,4,...,n-1,n 2,3,4,...,n−1,n,すなわちa[1,n]+a[2,n−1]a[1,n]+a[2,n−1]a[2,n−1]a[1,n]+a[2,n−1]

長さ3のa[1,2,3]+a[2,3,4]+a[3,4,5]+.a [ n − 3 , n − 2 , n − 1 ] + a [ n − 2 , n − 1 , n ] a[1,2,3]+a[2,3,4]+a[3,4,5]+...+a[n-3,n-2,n-1]+a[n-2,n-1,n] a[1,2,3]+a[2,3,4]+a[3,4,5]+...+a[n−3,n−2,n−1]+a[n−2,n−1,n]、第1項はa[1,2,3]a[1,2,3]a[1,2,3]の1,2,3,1,2,3,2,3,2,3,2,3,第2項は4 4 4 4,第3項は5,5,...最後の項はn n n nをa[1,n]a[1,n]a[1,n]a[1,n]をとる;2番目の残りの2,3,2,3,2,3,3番目の4 4,4番目の5,5,...最後のn−1 n−1得a[2,n−1]a[2,n−1]a[2,n−1]a[2,n−2]a[3,n−2]a[3,4番目の4,4,...最後の2番目のn−3 n−3 n−3 n−3,最後のn−2 n−2 n−2得:a[3,n−2]a[3,n−2]a[3,n−2]a[3,n−2]n−2を取り続ける.だから結論はw i w_i wi担当Σi=l r a isum_{i=l}^{r}a_iΣi=lr aiはa[1,n]+a[2,n−1]+である.a [ i , n − ( i − 1 ) ] , i ∈ [ 1 , ⌊ n + 1 2 ⌋ ] a[1,n]+a[2,n-1]+...+a[i,n-(i-1)],i\in[1,\lfloor\frac{n+1}{2}\rfloor] a[1,n]+a[2,n−1]+...+a[i,n−(i−1)],i∈[1,⌊2 n+1⌋]i>⌊n+1 2⌋i>lfloorfrac{n+1}{2}rfloor i>⌊2 n+1⌋:

長さがn n nの場合、a[1,n]a[1,n]a[1,n]a[1,n]

のみが考慮される

長さがn−1 n−1 n−1であることをさらに考慮すると、a[1,n−1]+a[2,n]=a[1,n]+a[2,n−1]a[1,n−1]+a[2,n]=a[1,n]+a[2,n]=a[1,n]+a[2,n]+a[2,n−1]a[1,n−−1]+a[2,n]=a[1,n]+a[2,n−1]

のみである

長さn−2 n−2 n−2 n−2 n−2をさらに考慮すると、a[1,n−2]+a[2,n−1]+a[2,n−1]+a[3,n]=a[1,n]+a[2,n−1]+a[3,n−2]+a[1,n−2]+a[2,n−2]+a[2,n−2]+a[2,n−1]+a[3,n]=a[1,n]=a[1,n]+a[2,n−1]+a[3,n−1]+a[3,n−2]+a[2,n−2]+a[2,n−2]+a[2,n−1]+a[3,n]+a[2,n−1]+a[3,n−2]は,長さが1 1 1,長さがn n n nのΣi=lr a isum_{i=l}^{r}a_iΣi=lr aiと同様,長さ2 2,長さn−1 n−1 n−1と同様,長さ3 3,長さn−2 n−2 n−2と同様である.長さi i iと長さn−(i−1)n−(i−1)n−(i−1)n−(i−1)は同じである.

注意:n n n nが奇数の場合、n+1 2⌋lfloorfrac{n+1}{2}rfloor{8970; 2 n+1⌋のΣi=lr a isum_{i=l}^{r}a_iΣi=lr aiと同じ長さです.
コード:

#include
using namespace std;

typedef long long ll;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
ll all[N], w[N];
int n;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld", &all[i]), all[i] += all[i - 1];
	for(int i = 1; i <= n; i++) scanf("%lld", &w[i]);
	
	ll temp = 0, res = 0;
	for(int i = 1; i * 2 <= n + 1; i++) {
		(temp += all[n - (i - 1)] - all[i - 1]) %= mod;
		(res += (w[i] + ((i * 2 == n + 1) ? 0 : w[n - (i - 1)])) * temp) %= mod;
	} 
	printf("%lld
", res);
	
	return 0;
}