传送门:https://ac.nowcoder.com/acm/contest/7329/D
题意
给长度为n的序列和一个d,分别在n个数中选k(1<=k<=n)个数,将这k个数增加d之后不影响排名,要求$ai+d<=aj$。 分别输出每一个k的概率。
思路
要是想在每个k中找出合法的方案,不管是正向的DFS还是反向的容斥,这都会导致T掉(主要是不会做,做了也会错)。看到n=5000时,O(n^2)的复杂度是可以的,那就可以考虑dp了。
设dp[i][j][1/0]表示前i个人中选了j个增加d,并且当前这一位选1/不选0。
所以就有两种选择,选或不选。
当前这一位没有被选,状态转移就是:
$dp[i][j][0] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] * (a[i - 1] + d <= a[i] )$
如果上一位被选了,这一就要判断上一位选了之后增加的d是否合法,合法就可要,不合法就不要。
当前这一位被选,状态转移就是:
$dp[i][j][1]=dp[i - 1][j- 1][0] + dp[i - 1][j-1][1]$
由于n=5000,dp[5000][5000][2]可能会爆掉,那么就需要用到滚动数组(因为转移只会与上一行有关)。
$设now=i\%2,pre =now \wedge 1,则状态转移为:$ $f[now][j][0] = f[pre][j][0] + f[pre][j][1] * (a[i - 1] + d <= a[i])$ $f[now][j][1] = f[pre][j - 1][0] + f[pre][j - 1][1]$
最后,预处理所有的阶乘、逆元、阶乘逆元。
Code(64ms)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113
| ##include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef long double ld; typedef pair<int, int> pdd;
##define INF 0x3f3f3f ##define lc t[u].ls ##define rc t[u].rs ##define m (l + r) / 2 ##define lowbit(x) (x & -x) ##define mid (t[u].l + t[u].r) / 2 ##define mem(a,b) memset(a , b , sizeof(a)) ##define FOR(i, x, n) for(int i = x;i <= n; i++)
const ll mod = 998244353;
const int N = 5005;
ll quick_pow(ll a, ll b) { ll ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans % mod; }
ll F[N + 10]; ll invF[N + 10]; ll invn[N + 10]; ll a[N + 10]; int vis[N + 10];
ll f[2][N][2];
inline void Init() { F[0] = F[1] = invF[0] = invF[1] = invn[0] = invn[1] = 1; for (int i = 2; i < N; i++) { F[i] = F[i - 1] * i % mod; invn[i] = (mod - mod / i) * invn[mod % i] % mod; invF[i] = invF[i - 1] * invn[i] % mod; } }
inline ll getC(int n, int k) { if (k < 0 n < 0 n > k) return 0; ll ans = F[k]; ans = ans * invF[n] % mod; ans = ans * invF[k - n] % mod; return ans; }
void solve() { Init(); int n, d; cin >> n >> d; for(int i = 1;i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); a[n + 1] = a[n] + d * 2; f[1][1][1] = 1; f[1][0][0] = 1; for(int i = 2;i <= n; i++) { int now = i % 2, pre = now ^ 1; mem(f[now], 0); for(int j = 0;j <= i; j++) { f[now][j][0] = (f[pre][j][0] + f[pre][j][1] * (a[i - 1] + d <= a[i])) % mod; f[now][j][1] = (f[pre][j - 1][0] + f[pre][j - 1][1]) % mod; } } int now = n % 2; for(int i = 1;i <= n; i++) { cout << (f[now][i][0] + f[now][i][1]) * quick_pow(getC(i, n), mod - 2) % mod << endl; } }
signed main() { ios_base::sync_with_stdio(false); ##ifdef FZT_ACM_LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); signed test_index_for_debug = 1; char acm_local_for_debug = 0; do { if (acm_local_for_debug == '$') exit(0); if (test_index_for_debug > 20) throw runtime_error("Check the stdin!!!"); auto start_clock_for_debug = clock(); solve(); auto end_clock_for_debug = clock(); cout << "Test " << test_index_for_debug << " successful" << endl; cerr << "Test " << test_index_for_debug++ << " Run Time: " << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl; cout << "--------------------------------------------------" << endl; } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug)); ##else solve(); ##endif return 0; }
|
本文作者:jujimeizuo
本文地址: https://blog.jujimeizuo.cn/2020/09/11/nowcoder-practice69-d/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!