F 求调
  • 板块学术版
  • 楼主rainygame
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/6/28 21:42
  • 上次更新2025/6/29 16:02:40
查看原帖
F 求调
804607
rainygame楼主2025/6/28 21:42

式子是不是:

fi=ji,ajaifi+aj>aifjaja1+1f_i=\dfrac{\sum\limits_{j\ne i,a_j\le a_i}f_i+\sum\limits_{a_j>a_i}f_ja_j}{\sum a-1}+1

然后按 aia_i 从小到大转移?

如果是,帮我看一下这份代码:

#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;
}

2025/6/28 21:42
加载中...