题解 | #序列求和#

考察知识点：数学、逆元

1^1+2^2+\dots+n^n = \frac{n(n+1)(2n+1)}{6}

证明方法有很多种，详情请见：

1²+2²+…+n²求和公式的推导有哪些方法? - 知乎

注意除 $6$ 时要使用逆元。

时间复杂度： $O (1)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define MOD 1000000007

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

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n = 1, inv6 = qpw(6, MOD - 2);
    // cin >> t;
    while (cin >> n)
    {
        n %= MOD;
        ll ans = n * (n + 1) % MOD * ((2 * n + 1) % MOD) % MOD;
        cout << ans % MOD * inv6 % MOD << endl;
    }
    return 0;
}