杭电多校第六场 1001 Road To The 3rd Building 题解

题目大意

输入n个可爱值，在1到n中任取起点和终点，定义可爱水平为起点到终点每个点的可爱值之和除以区间长度，随机选择一种方案，求可爱水平的期望值。

解题思路

真的不会写。。太难了。

看了几个题解，要么就是看不懂，要么就是没讲解。我太难了。。

最后终于找到了一个看懂了的题解，不容易啊。

首先，方案数为1到n的等差数列，和为$\Large \frac{n(n+1)}{2}$。

拿样例举例（咋样例都这么臭。。

对于: 1 1 4 5 1 4每个点的出现次数
len=1:1 1 1 1 1 1
len=2:1 2 2 2 2 1
len=3:1 2 3 3 2 1
−−−−−−−−−−−−−−
len=4:1 2 3 3 2 1
len=5:1 2 2 2 2 1
len=6:1 1 1 1 1 1

设$ans[i]$为长度为i的贡献，$sum[i]$为前缀和数组。

可以得出，前一半$ans[i]=ans[i-1]+sum[n-i+1]-sum[i-1]$。

后一半$ans[i]=ans[i-1]+sum[i]-sum[n-i]$。

初始化$ans[1]=ans[n]=sum[n]$。

如果n是偶数，单独考虑$\Large \frac{n}{2}+1$即可。

注意，在递推的时候，取余的时候需要加一个mod，虽然我知道是为了防止出现负数，但是我不知道为啥会出现负数。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 1e9 + 7, maxn = 2e5 + 5;
ll sum[maxn], ans[maxn];

ll qpow(ll a, ll b) {
    ll ans = 1;
    a %= mod;
    while (b) {
        if (b & 1)    ans = (ans * a % mod) % mod;
        a = (a * a) % mod, b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; scanf("%d", &t);
    while (t--) {
        ll n;
        scanf("%lld", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld", &sum[i]);
            sum[i] = (sum[i] + sum[i - 1]) % mod;
        }
        if (n & 1) {
            ans[1] = sum[n];
            for (int i = 2; i <= n / 2; i++)    ans[i] = (ans[i - 1] + sum[n - i + 1] - sum[i - 1] + mod) % mod;
            ans[n / 2 + 1] = (ans[n / 2] + sum[n / 2 + 1] - sum[n / 2]) % mod;
            ans[n] = sum[n];
            for (int i = n - 1; i > n / 2 + 1; i--)    ans[i] = (ans[i + 1] + sum[i] - sum[n - i] + mod) % mod;
        }
        else {
            ans[1] = sum[n];
            for (int i = 2; i <= n / 2; i++)    ans[i] = (ans[i - 1] + sum[n - i + 1] - sum[i - 1] + mod) % mod;
            ans[n] = sum[n];
            for (int i = n - 1; i > n / 2; i--)    ans[i] = (ans[i + 1] + sum[i] - sum[n - i] + mod) % mod;
        }
        ll res = 0;
        for (int i = 1; i <= n; i++)    res = (res + (ans[i] * qpow(i, mod - 2)) % mod) % mod;
        res = ((res * 2) % mod * qpow(n * (n + 1), mod - 2) % mod) % mod;
        cout << res << endl;
    }
    return 0;
}