１：通过不断缩小范围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：通过做差来的
i23456…a[i]332748118554580197665496237665496238554580200…d[i] = a[i]-a[i-1]2218320791109160401-110916038…dd[i] = d[i]-d[i-1]110916039110916039110916039…所以得到差的差是定值即可推出：
#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.群友忙猜，，，不懂： n 2 − 1 9 \frac{n^2-1}{9} 9n2−1%mod,然后除法取余用逆元 mod为质数可用费马小定理 n 2 − 1 9 \frac{n^2-1}{9} 9n2−1%mod等价于 ( n 2 − 1 ) ∗ 9 m o d − 2 (n^2-1)*9^{mod-2} (n2−1)∗9mod−2%mod 乘法取余可化为：( ( n 2 − 1 ) (n^2-1) (n2−1)%mod× 9 m o d − 2 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; }