2019 Multi-University Training Contest 2 1005（盲推规律

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=6595

题目描述：

题解：

盲推规律，贼强：

现今知道有三种：

１：通过不断缩小范围n pow(n,mod-i)来的

#include<cstdio>
#define ll long long
#define mod 998244353
ll pow_mod(ll a,ll b,ll c) {
    a = a % c;
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ans;
}
int main() {
    ll n;
    while (~scanf("%lld\n", &n)) {
        printf("%lld\n", ((n * n - 1) * pow_mod(3, mod - 3, mod) % mod));
    }
    return 0;
}

2：通过做差来的

所以得到差的差是定值即可推出：

#include<cstdio>
#define ll long long
#define mod 998244353
ll a[5000];
int main() {
    a[0] = 0;
    ll p = 110916039;
    ll pr = 332748118;
    for (int i = 1; i < 3002; i++) {
        a[i] = ((a[i - 1] + pr) % mod + mod) % mod;
        pr = (pr - p) % mod;
    }
    int n;
    while (~scanf("%d", &n)) {
        printf("%lld\n", a[n - 1]);
    }
    return 0;
}

3.群友忙猜，，，不懂：
$\frac{n^2-1}{9}$9n2−1​%mod,然后除法取余用逆元
mod为质数可用费马小定理 $\frac{n^2-1}{9}$9n2−1​%mod等价于 $(n^2-1)\ast 9^{mod-2}$(n2−1)∗9mod−2%mod
乘法取余可化为：( $(n^2-1)$(n2−1)%mod× $9^{mod-2}$9mod−2%mod)%mod

#include<cstdio>
#define ll long long
#define mod 998244353
ll pow_mod(ll a,ll b,ll c) {
    a = a % c;
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % c;
        a = a * a % c;
        b >>= 1;
    }
    return ans;
}
int main() {
    ll n;
    while (~scanf("%lld\n", &n)) {
        printf("%lld\n", (((n * n - 1) % mod * pow_mod(9, mod - 2, mod)) % mod));
    }
    return 0;
}