CSA Expected Max [dp+概率期望]

Description:

m m 个操作，nn个位置，每个操作会随机选一个位置加上 [0,c] [ 0 , c ] 中的随机值，问期望最大值。

Soution:

f[i][S][j] f [ i ] [ S ] [ j ] 表示第 i i 个人操作集合为SS，最大值为 j j 的概率，dp[i][S][j]dp[i][S][j]为前 i i 个人操作集合为SS，最大值为 j j <script type="math/tex" id="MathJax-Element-121">j</script>的概率，转移一下即可。

#include <bits/stdc++.h>
using namespace std;
const int P =  + ;
int n, m;
long long ans;
long long p[][][], dp[][ << ][], f[ << ][];
long long power(long long x, long long t) {
    long long ret = ;
    for(; t; t >>= , x = x * x % P) {
        if(t & ) {
            ret = ret * x % P;
        }
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int k = ; k <= ; ++k) {
        for(int i = ; i < m; ++i) {
            for(int j = ; j <= n; ++j) {
                scanf("%lld", &p[j][i][k]);
            }
        }
    }
    dp[][( << m) - ][] = ;
    for(int i = ; i <= n; ++i) {
        memset(f, , sizeof(f));
        f[][] = ;
        for(int S = ; S <  << m; ++S) {
            int c = __builtin_popcount(S);
            for(int j = ; j < m; ++j) {
                if(S >> j & ) {
                    break;
                }
                for(int k = c; k <=  * c; ++k) {
                    for(int d = ; d <= ; ++d) {
                        f[S ^ ( << j)][k + d] = (f[S ^ ( << j)][k + d] + f[S][k] * p[i][j][d] % P) % P;
                    }
                }
            }
        }
        for(int S = ; S <  << m; ++S) {
            int c = m - __builtin_popcount(S);
            for(int j = ; j <=  * c; ++j) {
                for(int S0 = S; ; S0 = (S0 - ) & S) {
                    int lim = __builtin_popcount(S0);
                    for(int k = lim; k <=  * lim; ++k) {
                        dp[i][S ^ S0][max(j, k)] = (dp[i][S ^ S0][max(j, k)] + dp[i - ][S][j] * f[S0][k] % P) % P;
                    }
                    if(!S0) {
                        break;
                    }
                }
            }
        }
    }
    for(int i = ; i <=  * m; ++i) {
        ans = (ans + dp[n][][i] * i % P) % P;
    }
    printf("%lld\n", ans * power((int) , L * (P - ) * m) % P);
    return ;
}