题解：CF2008F Sakurako's Box

Hhy140516 · 2025-08-11 17:18:36 · 题解

题目传送门

题意

发现 Q 就是 \frac{1}{2}n(n-1)，难点在于 P。

看样例，如果两两相乘，复杂度 O(n^2)，不可行；突然发现求这个东西在小学比较常见，当时是用到了乘法分配律来简化求解，这题同理。

答案为 \sum_{i=1}^n(a_i\times \sum_{j=i + 1}^na_j)，\sum_{j=i + 1}^na_j 可以用前缀和 sum_n-sum_i 来求解，所以 O(n) 求解即可。

这题还需求逆元，不会的看这里。

代码

/*
其实并不需要int128，只是调的时候的尝试
*/
#include<bits/stdc++.h>
using namespace std ;
const int MOD = 1e9 + 7 ;
__int128 n ;
__int128 sum[200005] , a[200005] ;
__int128 ksm(__int128 x , __int128 y)
{
  __int128 mul = 1 ;
  while(y)
  {
    if(y & 1) 
    {
      mul = mul * x % MOD ;
    }
    x = x * x % MOD ;
    y >>= 1 ;
  }
  return mul ;
}
void write(__int128 x)
{
  if(x > 9) {write(x / 10) ; putchar(x % 10 + '0') ;}
  else putchar(x % 10 + '0') ;
}
void solve()
{
  int x ;
  cin >> x ;
  n = x ;
  for( int i = 1 ; i <= n ; i++ ) 
  {
    int x ;
    cin >> x ;
    a[i] = x ;
  }
  for( int i = 1 ; i <= n ; i++ ) sum[i] = (sum[i - 1] + a[i]) ; // 前缀和
  __int128 ans = 0 ;
  for( int i = 1 ; i < n ; i++ )
  {
    ans += a[i] * ((sum[n] - sum[i])) ; // 记录P
  }
  write(ans * ksm(n * (n - 1) / 2 , MOD - 2) % MOD) ; // 逆元
  cout << "\n" ;
}
int main()
{
  int t = 1 ;
  cin >> t ; // 多组
  while(t--) solve() ;
  return 0 ;
}