题解 P5389 [Cnoi2019]数学课

发表于 | 分类于 | 阅读次数：

题面
根据$\sum_{i=1}^n i^2 = \frac{n(n+1)(2\times n+1)}{6}$
可以把题目所求化为$\frac 12\times (1-\frac{3}{n(n+2)})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int main() {
    long long n;
    scanf("%lld", &n);
    n %= mod;
    if(n == 0) return cout << (mod + 1) / 2 << endl, 0;
    long long res = 2 * n % mod * (n + 2) % mod, ans = 1;
    for(int b = mod - 2; b; b >>= 1, res = res * res % mod) if(b & 1) ans = ans * res % mod;
    ans = ans * 3 % mod;
    ans = ((mod + 1) / 2 - ans + mod) % mod;
    return cout << ans << endl, 0;
}