百度之星 (2022-09-10)

2022 百度之星复赛，记一下这两题。

A. 子序列

题意

把数组分成若干个非空递增子序列，求最大的总得分。

思路

每个数单独放成一个子序列就能取到上界，答案直接是数组元素之和。读入后累加，注意总和用 long long。

代码

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;


void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

ll ans;

void solve() {
    int x;
    scanf("%d", &x);
    ans += x;
}

int main() {
    int T;
    // T = 1;
    scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    printf("%lld\n", ans);
    return 0;
}

C. 最大值

题目链接

题意

长度为 $n$ 的数组，每个数都在 $[1,m]$ 内。一个数组的权值是等于最大值的元素个数，求所有数组的权值之和，对 $998244353$ 取模。保证 $nm\le10^{12}$ 。

思路

固定一个位置，假设它的值是 $x$ ，并且它是最大值，那么其他位置都可以从 $1$ 到 $x$ 随便选，共 $x^{n-1}$ 种。每个位置的贡献一样，所以答案是

$n\sum_{x=1}^{m}x^{n-1}.$

$n,m$ 至少有一个不超过 $10^6$ 。 $m$ 小就直接快速幂求和；否则 $n$ 小，幂和是 $n$ 次多项式，算出 $0$ 到 $n$ 的值后做拉格朗日插值。

代码

#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

typedef long long ll;
typedef pair<int, int> pii;

const ll mo = 998244353;

inline ll fpow(ll x, ll y) {
    ll res = 1; for(; y; y >>= 1, x = x * x % mo) if(y & 1) res = res * x % mo; return res;
}

void debug(int x) {
    printf("??? %d\n", x);
}

void debug(int *X, int x) {
    printf("??? ");
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
}

ll n, m, ans;

void solve() {
    // cout << fpow(4, 3) << endl;
    cin >> n >> m;
    ans = 0;
    if(m <= n) {
        for(ll i = 1; i <= m; i++) ans = (ans + fpow(i, n - 1)) % mo;
    }
    else {
        int k = n;
        vector<ll> y(k + 1), fac(k + 1), pre(k + 2), suf(k + 2);
        for(int i = 1; i <= k; i++) y[i] = (y[i - 1] + fpow(i, n - 1)) % mo;
        ll x = m % mo;
        if(x <= k) ans = y[x];
        else {
            fac[0] = 1;
            for(int i = 1; i <= k; i++) fac[i] = fac[i - 1] * i % mo;
            fac[k] = fpow(fac[k], mo - 2);
            for(int i = k; i >= 1; i--) fac[i - 1] = fac[i] * i % mo;
            pre[0] = suf[k + 1] = 1;
            for(int i = 0; i <= k; i++) pre[i + 1] = pre[i] * (x - i + mo) % mo;
            for(int i = k; i >= 0; i--) suf[i] = suf[i + 1] * (x - i + mo) % mo;
            for(int i = 0; i <= k; i++) {
                ll tmp = y[i] * pre[i] % mo * suf[i + 1] % mo;
                tmp = tmp * fac[i] % mo * fac[k - i] % mo;
                if((k - i) & 1) ans = (ans - tmp + mo) % mo;
                else ans = (ans + tmp) % mo;
            }
        }
    }
    ans = ans * (n % mo) % mo;
    cout << ans << endl;
}

int main() {
    int T;
    T = 1;
    // scanf("%d", &T);
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

A. 子序列

题意

思路

代码

C. 最大值

题意

思路

代码

Random Posts