加训

CCPC威海2020E：

　　考虑状压， 用g[S][i]表示长为i的序列，S里的怪物都活着的方案数，用f[S][i]表示常为i的序列， S里的怪物都被砍死的概率。

　　状态g很好转移， 做一个背包dp即可

　　然后考虑转移， 我们只需要考虑S最后一个杀死的是谁， 在哪里杀死的， 假设在i杀死， 杀死乐k， 那么它可以从f[S2][i-1]转移过来， 然后在S2的j-sum[S2]个空位中选出a[k]-1个位置， 然后在i的位置放上最后一个k

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 using ll = long long;
 4 using pii = pair<int,int>;
 5 using LL = __int128;
 6 #define ln '\n'
 7 #define pb push_back
 8 #define double long double
 9 
10 const int N = 105;
11 int n, m, a[N], sum[1<<15], cnt[1<<15];
12 double C[N][N], g[1<<15][105], f[1<<15][105], tmp[1<<15];
13 
14 int main(){
15     ios::sync_with_stdio(false);
16     cin.tie(nullptr);
17     cout.tie(nullptr);
18     cin >> n >> m;
19     for(int i=0; i<n; i++)
20         cin >> a[i];
21 
22     for(int j=0; j<(1<<n); j++)    
23         for(int i=0; i<n; i++)
24             if((j>>i)&1) {
25                 sum[j] = sum[j^(1<<i)] + a[i];
26                 cnt[j]++;
27             }
28 
29     for(int i=0; i<=m; i++){
30         C[i][0] = 1;
31         for(int j=1; j<=i; j++){
32             C[i][j] = C[i-1][j] + C[i-1][j-1];
33             // cout << C[i][j] << " \n"[j==i];
34         }
35     }
36 
37     g[0][0] = 1;
38     for(int S=0; S<(1<<n); S++){
39         //预处理g[S][i]表示用S里的元素，用了i个，都没死掉的方案数
40         // g[S][0] = 1;
41         for(int i=0; i<n; i++)
42             if((S>>i)&1){
43                 int S2 = S^(1<<i);
44                 for(int j=0; j<=m; j++){
45                     for(int k=0; k<=min(a[i]-1, j); k++){
46                         // cout << j << " " << k << " " << C[j][k] << "--" << ln;
47                         g[S][j] += g[S2][j-k] * C[j][k];
48                     }
49                     // cout << S << " " << j << " " << g[S][j] << ln;
50                 }
51                 break;
52             }
53     }
54 
55     f[0][0] = 1;
56     for(int S=0; S<(1<<n); S++){
57         //f[S][i]砍i刀， S死掉的概率
58         for(int now = sum[S]; now < m; now++){
59             for(int i=0; i<n; i++){
60                 if(((S>>i)&1)^1){
61                     if(a[i]-1 <= now-sum[S])
62                         f[S^(1<<i)][now+1] += f[S][now]*C[now-sum[S]][a[i]-1] / (n-cnt[S]);
63                     //杀死一个新人
64                 }
65             }
66             f[S][now+1] += f[S][now] / (n - cnt[S]);//放一个空的在自己后面
67         }
68     }
69 
70     double ans = 0;
71     for(int S=0; S<(1<< n); S++){
72         for(int i=sum[S]; i<=m; i++)
73             f[S][i] *= g[((1<<n)-1)^S][i-sum[S]];
74         ans += f[S][m] * cnt[S];
75     }
76 
77     cout << fixed << setprecision(10) << ans << ln;
78 }