• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 2021牛客多校第一场 I题(DP)

4小时前 2次浏览

## 代码

``````#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
constexpr int N = 5005;
const int MOD = 998244353;

int T, n;
int p[N], c[N], sum[N], pos[N], inv[N];
int dp[N][N];

int qpow(int x, int k) {
int ret = 1;
while(k) {
if(k & 1)  ret = (ll) ret * x % MOD;
x = (ll) x * x % MOD;
k >>= 1;
}
return ret;
}

int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &p[i]);
pos[p[i]] = i;
inv[i] = qpow(i, MOD - 2);
}
for(int j = n; j > 0; --j) {
for(int i = 0; i <= n; ++i)  c[i] = sum[i] = 0;
for(int t = j + 1; t <= n; ++t) {
c[pos[t]] = 1;
sum[pos[t]] = dp[j][t];
}
for(int i = n - 1; i >= 0; --i) {
c[i] += c[i + 1];
sum[i] = (sum[i] + sum[i + 1]) % MOD;
}
for(int i = j - 1; i >= 0; --i) {
int tot = c[pos[i]];
int sm = sum[pos[i]];
if(tot)  dp[i][j] = ((ll) inv[tot] * sm + 1) % MOD;
}
}
int ret = 0;
for(int i = 1; i <= n; ++i)  ret = (ret + dp[0][i]) % MOD;
printf("%lld", ((ll) ret * inv[n] % MOD + 1) % MOD);
}``````