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. 最大值
题意
长度为 的数组，每个数都在 内。一个数组的权值是等于最大值的元素个数，求所有数组的权值之和，对 取模。保证 。
思路
固定一个位置，假设它的值是 ，并且它是最大值，那么其他位置都可以从 到 随便选，共 种。每个位置的贡献一样，所以答案是
至少有一个不超过 。 小就直接快速幂求和；否则 小，幂和是 次多项式，算出 到 的值后做拉格朗日插值。
代码
#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;
}