关于月赛T2,推了好几遍式子都找不出来错,为啥死活过不去?
  • 板块学术版
  • 楼主Starlight237
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/10/18 23:32
  • 上次更新2023/11/5 10:25:45
查看原帖
关于月赛T2,推了好几遍式子都找不出来错,为啥死活过不去?
75765
Starlight237楼主2020/10/18 23:32
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define ll long long
const int mod = 998244353;
ll dp[2000001];
inline int qpow(int x, ll b) {
	reg int res = 1;
	for (; b; b >>= 1, x = (ll)x * x % mod) (b & 1) && (res = (ll)res * x % mod);
	return res;
}
int main() {
	ll n, m;
	scanf("%lld%lld", &n, &m);
	if (m == 0) {
		n %= mod, m %= mod;
		printf("%lld", (n * (n + 1) / 2 + n) % mod);
		return 0;
	} 
	ll tt = n + m;
	dp[n] = (n * (n + 1) / 2 + n) % mod;
	for (reg int i = n + 1; i <= tt; ++i)
		dp[i] = ((ll)(i - n) * qpow(i, mod - 2) % mod * (dp[i - 1] + 1) % mod + n * (i + 1) / 2 % mod + n) % mod;
	printf("%lld", dp[tt]);
	return 0;
}

理论上进一步矩阵快速幂可以AC

2020/10/18 23:32
加载中...