概率与期望,组合
分类:
IT文章
•
2022-08-30 15:01:36
1.一个图论套路,结合之前的小知识(枚举子集)
例:Online judge 1268,Online judge 1396
询问一个图连通的方案数时,可令Dp一维为图是否连通,另一维是图的二进制表示(完全图可简化为点的个数),从而$Dp[x][0]$可通过$Dp[y][1]$来转移$ysubset x$
具体来说,可令$x$中任意一个点为定点,枚举其中包含的联通块,同时其他点与该联通块之间不会有线段连接,按照题意列出方程可做到不重不漏。之后通过全集求出$Dp[x][1]$
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 2001, MOD = 998244353;
int h[MAXN], g[MAXN], f[MAXN], exp2[MAXN], c[MAXN][MAXN], n, k;
int ask(int x){
memset(g, 0, sizeof(g));
g[0] = 1;
for(int i=1; i<=n; i++)
for(int j=1; j<=min(i,x); j++)
g[i] = ((long long)c[i-1][j-1] * f[j] % MOD * g[i-j] + g[i]) % MOD;
return g[n];
}
int main(){
n = read(), k = read();
exp2[0] = 1, h[0] = 1;
for(int i=1; i<=n; i++)
exp2[i] = exp2[i-1] * 2 % MOD, h[i] = (long long)h[i-1] * exp2[i-1] % MOD;
for(int i=0; i<=n; i++){
for(int j=0; j<=i; j++)
if(j == 0 || j == i) c[i][j] = 1;
else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
}
f[1] = 1;
for(int i=2; i<=n; i++){
f[i] = h[i];
for(int j=1; j<i; j++)
f[i] = (-(long long)c[i-1][j-1] * f[j] % MOD * h[i-j] + f[i]) % MOD;
if(f[i] < 0) f[i] += MOD;
}
int ans = (ask(k) - ask(k-1)) % MOD;
if(ans < 0) ans += MOD;
printf("%d", ans);
return 0;
}
View Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 11, MAXM = 101, SIZE = 1 << (MAXN - 1);
long long c[MAXM][MAXM], dp[MAXM][SIZE][2];
int cnt[SIZE], g[MAXN][MAXN];
int main(){
int n = read(), m = read(), size = (1 << n) - 1;
for(int i=1; i<=m; i++){
int x = read() - 1, y = read() - 1;
g[x][y] = g[y][x] = 1;
}
for(int i=0; i<=m; i++)
for(int j=0; j<=i; j++)
c[i][j] = (j == 0 || j == i) ? 1 : c[i-1][j] + c[i-1][j-1];
for(int i=0; i<=size; i++)
for(int j=0; j<n; j++) if(i & (1<<j))
for(int k=j+1; k<n; k++) if(i & (1<<k))
if(g[j][k]) cnt[i]++;
for(int i=0; i<n; i++)
dp[0][1<<i][1] = 1;
for(int i=0; i<=size; i++)
dp[0][i][0] = c[cnt[i]][0] - dp[0][i][1];
for(int i=1; i<=m; i++){
for(int j=0; j<=size; j++){
int u = j & (-j);
for(int k=(j-1)&j; k; k=(k-1)&j) if(k & u)
for(int p=0; p<=i; p++)
dp[i][j][0] += dp[p][k][1] * c[cnt[j-k]][i-p];
dp[i][j][1] = c[cnt[j]][i] - dp[i][j][0];
}
}
double ans = 0;
for(int i=0; i<m; i++)
ans += (double)dp[i][size][0] / c[m][i];
printf("%.6lf", ans / (m + 1));
return 0;
}
View Code
2.卡特兰数
例:hdu 5184
卡特兰数可从一维扩展为二维,具体体现为:有$n$个$0$和$m$个$1$的数构成的队列,其中保证任意时刻$0$的个数大于$1$的个数,求最后的方案数
若保证$0$的个数等于$1$的个数,答案就是标准的卡特兰数$ans=frac{C_{2n}^{n}}{n+1}$,当个数不确定时,$ans = C_{n+m}^{n}-C_{n+m}^{n+1}$,相当于一个二维的卡特兰数
3.第一类斯特林数
第一类斯特林用于求一些十分古怪的模型
例:hdu 4372
将最高的建筑请况讨论之后(组合),要将剩下的建筑插入到这些建筑之中,这时就有了疑惑,首先这不是集合,建筑之间有序,可以将一组建筑中最高的哪一个建筑作为标志,剩下的建筑放在这个建筑的右边,这样就形成了一个环,转化为了第一类斯特林数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 2001, MOD = 1e9+7;
int c[MAXN][MAXN], s[MAXN][MAXN];
int main(){
for(int i=0; i<MAXN; i++){
c[i][0] = c[i][i] = 1;
s[i][0] = 0, s[i][i] = 1;
for(int j=1; j<i; j++){
c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
s[i][j] = ((long long)(i-1) * s[i-1][j] % MOD + s[i-1][j-1]) % MOD;
}
}
int T = read();
while(T--){
int N = read(), F = read(), B = read();
printf("%d
", (long long)c[F-1+B-1][F-1] * s[N-1][F-1+B-1] % MOD);
}
return 0;
}
View Code
4.概率与期望的dp转移
1.常规转移(题目十分少见),且多半是水题,例如:hdu 4405 没有其它技巧,直接dp。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 100020;
double Dp[MAXN];
int last[MAXN];
int main(){
memset(last, -1, sizeof(last));
while(1){
int n = read(), m = read();
if(n == 0 && m == 0)
break;
for(int i=1; i<=m; i++){
int x = read(), y = read();
last[x] = y;
}
for(int i=n; i<=n+5; i++)
Dp[i] = 0;
for(int i=n-1; i>=0; i--){
if(last[i] != -1) Dp[i] = Dp[last[i]];
else Dp[i] = 1 + (Dp[i+1] + Dp[i+2] + Dp[i+3] + Dp[i+4] + Dp[i+5] + Dp[i+6]) / 6;
}
printf("%.4lf
", Dp[0]);
for(int i=0; i<=n; i++)
last[i] = -1;
}
return 0;
}
View Code
2.高级转移,dp转移表达式中包含其本身,例:hdu 3853,记得在转移的时候需要判断分母是否为0.
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 1001;
double Dp[MAXN][MAXN], a[MAXN][MAXN][3];
int main(){
int r, c;
while(scanf("%d%d", &r, &c) != EOF){
memset(Dp, 0, sizeof(Dp));
for(int i=1; i<=r; i++)
for(int j=1; j<=c; j++)
for(int k=0; k<3; k++)
scanf("%lf", &a[i][j][k]);
for(int i=r; i>=1; i--){
for(int j=c; j>=1; j--){
if(i == r && j == c)
continue;
if(abs(1 - a[i][j][0]) < 1e-7)
continue;
Dp[i][j] = (a[i][j][1] * Dp[i][j+1] + a[i][j][2] * Dp[i+1][j] + 2) / (1 - a[i][j][0]);
}
}
printf("%.3lf
", Dp[1][1]);
}
return 0;
}
View Code
3.变态转移,dp转移有后效性,例:hdu 4089 这时需要谨慎的观察,通过某种消元方法将后效性除去(最坏就只有高斯消元了),一般来说未知数都是环形的,一轮遍历就能求解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
long long read(){
long long ans = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
f *= (ch == '-') ? -1 : 1, ch = getchar();
do ans = (ans << 1) + (ans << 3) + (ch ^ 48), ch = getchar();
while(isdigit(ch));
return ans * f;
}
const int MAXN = 2001;
double Dp[MAXN][MAXN];
int main(){
int N, M, K;
double p1, p2, p3, p4;
while(~scanf("%d%d%d%lf%lf%lf%lf",&N,&M,&K,&p1,&p2,&p3,&p4)){
if(1 - p1 <= 1e-6 || p4 <= 1e-6){
printf("%.5lf
", 0);
continue;
}
p2 /= (1 - p1), p3 /= (1 - p1), p4 /= (1 - p1);
for(int i=1; i<=N; i++){
double k = 1, b = 0;
for(int j=1; j<=i; j++)
b = b * p2 + (j <= K) * p4 + Dp[i-1][j-1] * p3, k *= p2;
Dp[i][i] = b / (1 - k);
Dp[i][1] = Dp[i][i] * p2 + p4;
for(int j=2; j<i; j++)
Dp[i][j] = Dp[i][j-1] * p2 + Dp[i-1][j-1] * p3 + (j <= K) * p4;
}
printf("%.5lf
", Dp[N][M]);
}
return 0;
}