「2022 远光杯」随机播放
2022/6/9 23:20:06
本文主要是介绍「2022 远光杯」随机播放,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
一道典型的 概率DP
由于手算复杂度为 \(O(n^2 m k)\) 约为 \(3.2 \times 10^9\), 赛时没敢写
定义 \(f[i][j][k]\) 表示选择了 \(i\) 个物品,当前物品为 \(j\),并且出现了 \(k\) 次 第\(t\)首歌曲的概率。
然后进行状态转移即可
// #23. 「2022 远光杯」随机播放 // URL: https://oj.kexie.club/problem/23 // Memory Limit: 256 MB // Time Limit: 1000 ms // #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for(int i(a); i <= b; i ++) #define dec(i, a, b) for(int i(a); i >= b; i --) template <typename T> inline void chkmax(T &x, T y) { x = max(x, y); } template <typename T> inline void chkmin(T &x, T y) { x = min(x, y); } constexpr int N = 4010; constexpr int mod = 1e9 + 7; ll f[2][11][N]; ll pp[11], np[11]; ll sum, inv; ll ksm(ll a, ll b, ll ret = 1) { while(b) { if(b & 1) ret = ret * a % mod; b >>= 1; a = a * a % mod; } return ret; } void solve() { int n, m, t, k; cin >> n >> m >> t >> k; rep(i, 1, n) cin >> pp[i], sum += pp[i]; rep(i, 1, n) np[i] = ksm(sum - pp[i], mod - 2); inv = ksm(sum, mod - 2); rep(i, 1, n) { f[1][i][i == t] = pp[i] * inv % mod; } rep(i, 2, m) { memset(f[i & 1], 0, sizeof f[i & 1]); rep(j, 1, n) { rep(p, 0, min(k, i - 1)) { rep(q, 1, n) if(j != q) { ll &ret = f[i & 1][q][p + (q == t)]; ret += f[(i + 1) & 1][j][p] * pp[q] % mod * np[j] % mod; ret %= mod; } } } } ll ans = 0; rep(i, 1, n) { ans += f[m & 1][i][k]; ans %= mod; } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; } /* * * ┏┓ ┏┓+ + * ┏┛┻━━━┛┻┓ + + * ┃ ┃ * ┃ ━ ┃ ++ + + + * ████━████+ * ◥██◤ ◥██◤ + * ┃ ┻ ┃ * ┃ ┃ + + * ┗━┓ ┏━┛ * ┃ ┃ + + + +Code is far away from * ┃ ┃ + bug with the animal protecting * ┃ ┗━━━┓ 神兽保佑,代码无bug * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ + + + + * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛+ + + + */
这篇关于「2022 远光杯」随机播放的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?