概率期望DP
概率DP
概率
例题1
https://codeforces.com/contest/540/problem/D
题意：
共有三个物种a,b,ca,b,ca,b,c，每个物种的数量分别为nnn, mmm, kkk，其中aaa 能吃 bbb，bbb 能吃 ccc，ccc 能吃 aaa，求最后只剩下一种物种时的概率。
解法:
设f[i][j][k]f[i][j][k]f[i][j][k] 表示当前剩余iii个 aaa 物种，jjj个 bbb 物种，kkk个 ccc 物种。
由题意，有f[n][m][k]=1f[n][m][k]=1f[n][m][k]=1。
枚举三种情况发生的概率，递推即可。f[i][0][0],f[0][i][0],f[0][0][i]f[i][0][0],f[0][i][0],f[0][0][i]f[i][0][0],f[0][i][0],f[0][0][i]为最终答案。
代码：
123456789101112131415f[n][m][k] = 1.0;for (int i = n; i >= 0; -- i) { for (int j = m; ...
无题
容斥原理
UVA - 11806
题意：
求在一个n*m的矩阵中选择k个，使得每个边界上至少有一个被选择。
做法：
容斥。
代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354const int N = 5e3 + 7, mod = 1e6 + 7;int fact[N],inv[N];int n, m, k;int c[N][N];int qmi(int a,int b) { int res = 1ll % mod; while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res % mod;}int C(int n,int m) { return c[n][m];}void init( ...
2021昆明
2021昆明
H Hard Calculation
签到
I Mr. Main and Windmills
题意：
给出n个点和一条直线，点两两之间形成一条直线，询问m次，每次询问点之间直线与原来直线的第k个交点。
做法：
求直线与线段交点。
代码：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103#include <bits/stdc++.h>#define int long long #define endl '\n'#define ff doubleusing namespace std;const int N = 2e5 + 7;const ff eps = 1e-9;ff x[N], y[N] ...
Kininged_Record_2022_2
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX19JTExOZsMyYcaaC3MIH8D50p6kqQrpN0tvV+FpULZBJD36rz8DGT+GwS+35f6FPxTofuqAwEh7Izw0TP7iovPgF5eimlsXZdUqOFvrGJZlgaKSeQjiQI/3hcLfzvh/UYH9VUUQG+FT/O2Z44MHV5leFHf8z3LN19pqBvsDVHwiR8/UhElQqqUsxo8FRiqlL6+0RGvml+vew1OVV1oHGlQyAao7zKYox51ZVBSmSxPDpNhtHGdq4++iLK0Rwa7gUybfYH8dhAu4KAvfQH5sp/ABLLHONHkcI6taEeBQumc8P74iTsph4/JzzoJ32y4ADsA+7Zd+2cRLZ8ZKwBsBA4ETjPkj6YKn5qGa8RnDEH/gtPE3/FDu8ddsiZsXvY2W2cmbP3O8bVXettfJQx65rFY5WsWO7ZCb ...
forink
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX19LTjPrYmYonxsUz5QhZf9RAc2IQwE3TVr6lEeYfLoqNmT/jZu8duTT9GzW2DFf6W05JPn9M1h3TpM1AdhCJ5ETW7l9jfzR0znOBw7mftyYta45R0haumpw+ZfXpoBWSuC9a5pIoKea4fUixZmUZE3Z87IHbUIJlSx4vH4U2uo1Ou/YU/XzeHY/aW9ndwOcI1rFGgr5MlBnzeFaThDzZXLnaco2Pj7OegzdXYBdOkm9/XaY/hPGB2zY3jDCJgev11BsSzy5WyDIGpmSeZbbPYth8zrGzejUYqYsP4TxOhG1+98RFY09glF5GwP9PDmLLKOzJRIUZB79F/O6Jsvznglnew9NlEK3O/BGn/BLYccIgcZC8hy5tefoZK7EymM6TrTXtpwX3cGL146ziWtNkjh0Xn7Pdqh0 ...
Kininged_Record_2022_1
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX19SrlBYqoTrC+thXVIcx55Ww8KtYsPo8MS8g87Gex0rm0Gx2mtFZ3pZETk4DH285iZkG5PsAE3/OheLP4AuvTKLhDnaSwfwOxBEcnlL6HSZG+aq7vToy1FE6nrAcmrJnlXWzvJ63EscFwdFe356fb/+kCZnnRTll65WQiP+OSLpDIMmlKtbU+wovhOJ76fJblOdlqh8x4cosueGXQpiKqGndFsTQNwvDVrImy9J0v0D3MiwOTe383a8qOzZr6gIDHeBtCFqQ04b+oxR8DGklhsJ6sDEbPqJGeBozELBBwLhckIc8puhTh2FVIUg66WDyF5Wt/T6sv9HLlXi6L0sBmkDQzzux8S06kNvI2UDEF9WI+Rp35CXJOwzR/mU/3LmR8VRNB48klDEvZFQLeGYcN3X7oZ1hOvW ...
team_work_1
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX1/UrAPemWCJY8j5q+ABf7AWoJTH+p245MWd20jDmAo0JI4Wbl1vSMfAvpaVgP8ErXdlFED7cql06rTel28dzzHWES+OYbrW2uZB0LVnMhnYnwGvAvthp8/CWq301mUHr3bjzv2EnjKU07Ydu1momWHSzfRyRguxtpSskhR0X03aVJQZJka5we/CWNdcKOxzIZH/RI6zz9SMUkciW3FgRqw8q0RDTiZffczH/Ws+0cwB1VTA0FesS1IjpT/LdyoE0fFSIzBB+rH76NgHqxin1Q0zCVb718UvhTa3TxbNleXLD9GuYfpXgqPtjFkZ5eUMLu7iYiKquRcxYI2PefwFHg2IdSyeiJ3H2WvER+QRaveOzmeKysGJYBh3wO5Ot3FDJ1mbYqS00cRFHPDY0xNsA+4lG+Nk3PC6 ...
Kininged_Record_2021_12
Kininged 2021.12 Record
摆烂月
Kininged_Record_2021_11
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX1+wTieorCf3mC8bsAQia+ifvztzTtqXSUfCxur4YGlDciL0B6nq0+sivY/5M4//0dNfFWfl4tQms2I6oP6xEi+fkuDDXG57ExR5gZZnrkw5V51XyrWb0aWjrcWoHFOy0poDTnEaDWj6vutVBi9zxAlNaLyllN2UZqs87uInHiVDLULg5FcNL5WSdy+NnAKPL4wR/E2OGdjSAG/EvAPPP1CkRuP3bMLUpv6jnLSQKYg37x8Q+Z8oKiFQzmyjds5zCKOXhAxg2RW8j2/0SNDcipsqiV4pFrYrvIlRxWBkMdl/IP5VBtfmnVpUafim3WJoUGfIAJkogDV4VJMyyldMc3IwwsKqx7GPGSihe94JZZaGXK70tp+AmH+FuK5+PzsHvmnYVXkat++j498ZM3AX0tht3UtTqSia ...
SCR1
输入密码，查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX1/EiHLxo5h19uUNL/63rUZZb9krVfKcULjupB+CCM8OgQcpG4AAZGzmJK/wP+cu5tw1H5YW/SCfJN/doZkXKRtpZi1JL5VnxQhSwM3xATVx5bZOmERjHfl0UdJgSGQGz5H+nwY5IiVd16oXCYlK1BuE3A3NqVWMTH9K2FY7A8RbkBEwma9r1kp9r0AmEeuQnnpFDEJ96Jg7VMBACFU+9LDsLW/Xmzex/ZoImxcl7m4F1Yte2XQQH/E3ZiCvlvFcsrl2TSSIrWlmOOCO+XNGiXiKmsg6hzuBdNg0CJK14qa759GkRWWMChcJydAPyMxq4OmksH39DAPo0F70sABNSx9IjYnol7Dc/uVJOxgkzczjBRqeNXo2vzPe6lGYgTuwRrgMWY1Tv/9fiNw2Xie42d/SDvGN091p ...