式子是不是:
fi=∑a−1j=i,aj≤ai∑fi+aj>ai∑fjaj+1然后按 ai 从小到大转移?
如果是,帮我看一下这份代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 300005
const int MOD(998244353);
int n, k, sm; int a[MAXN], id[MAXN], s[MAXN], f[MAXN];
int qpow(int x, int k=MOD-2){int res(1); for (; k; k>>=1, (x*=x)%=MOD) if (k&1) (res*=x)%=MOD; return res;}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> k; for (int i(1); i<=n; ++i) cin >> a[i], (sm += a[i]) %= MOD; iota(id+1, id+n+1, 1);
sort(id+1, id+n+1, [](int x, int y){return a[x] < a[y];});
for (int i(1); i<=n; ++i) s[i] = (s[i-1]+a[id[i]]) % MOD;
for (int i(n); i>1; --i) if (a[id[i]] == a[id[i-1]]) s[i-1] = s[i];
for (int i(1); i<=n; ++i) (s[i] += MOD-a[id[i]]) %= MOD;
for (int i(n), lst(0), sum(0); i; --i){
if (i != n && a[id[i+1]] != a[id[i]]){
for (int p(i+1); ; ++p){
(sum += f[id[p]]*a[id[p]]%MOD*qpow(sm-1)) %= MOD;
if (a[id[p]] != a[id[p+1]]) break;
}
}
f[id[i]] = (sum+1)*qpow((MOD+1-s[i]*qpow(sm-1)%MOD)%MOD)%MOD;
}
cout << f[k];
return 0;
}