RandomPaintingOnABoard

\(n\times m\) 的棋盘，每个位置有 \(p_{i,j}\)。每轮 \((i,j)\) 被选中的概率为 \(\frac{p_{i,j}}{sum}\)。

问?少?轮后每???列?少?个被选中。

\(nm\leq 150,\max\{n,m\}\leq 21,0\leq p_{i,j}\leq 9\)。

题解

显然是min-max容斥。如何DP呢？

注意到 \(nm\leq 150\)，那么 \(\min\{n,m\}\leq 12\)。假设行数更小，那么我们可以暴力枚举行的子集，对列做DP。

\(dp(i,j,k)\) 表示前 \(i\) 列，\(\sum p=j\)，奇偶性为 \(k\) 的方案数。1行0列的时候贡献系数应为正。

时间复杂度 \(O(2^n m~sum~n)\)。

int a[21][21];
LD f[2][1351];

class RandomPaintingOnABoard{
public:
    LD expectedSteps(CO vector<string>&prob){
        int n=prob.size(),m=prob[0].size();
        if(n<=m){
            for(int i=0;i<n;++i)for(int j=0;j<m;++j)
                a[i][j]=prob[i][j]-'0';
        }
        else{
            for(int i=0;i<n;++i)for(int j=0;j<m;++j)
                a[j][i]=prob[i][j]-'0';
            swap(n,m);
        }
        int tot=0;
        for(int i=0;i<n;++i)for(int j=0;j<m;++j)
            tot+=a[i][j];
        LD ans=0;
        for(int s=0;s<1<<n;++s){
            int cur=0,sum=0;
            for(int i=0;i<n;++i)if(s>>i&1){
                cur^=1;
                for(int j=0;j<m;++j) sum+=a[i][j];
            }
            memset(f,0,sizeof f),f[cur][sum]=1;
            for(int j=0;j<m;++j){
                int sum=0;
                for(int i=0;i<n;++i)if(~s>>i&1)
                    sum+=a[i][j];
                for(int i=tot;i>=sum;--i){
                    LD x=f[0][i-sum],y=f[1][i-sum];
                    f[1][i]+=x,f[0][i]+=y;
                }
            }
            for(int i=1;i<=tot;++i) ans+=(f[1][i]-f[0][i])*tot/i;
        }
        return ans;
    }
};

//int main(){
//  vector<string> prob=
//  {"000000000000001000000",
//   "888999988889890999988",
//   "988889988899980889999",
//   "889898998889980999898",
//   "988889999989880899999",
//   "998888998988990989998",
//   "998988999898990889899"};
//  RandomPaintingOnABoard tmp;
//  LD ans=tmp.expectedSteps(prob);
//  printf("%.10Lf\n",ans);
//  return 0;
//}

随机游走

给定一棵 \(n\) 个结点的树，你从点 \(x\) 出发，每次等概率随机选择一条与所在点相邻的边走过去。

有 \(Q\) 次询问，每次询问给定一个集合 \(S\)，求如果从 \(x\) 出发一直随机游走，直到点集 \(S\) 中所有点都至少经过一次的话，期望游走几步。

特别地，点 \(x\)（即起点）视为一开始就被经过了一次。

答案对 $998244353 $ 取模。

对于 \(100\%\) 的数据，有 \(1\leq n\leq 18\)，\(1\leq Q\leq 5000\)，\(1\leq k\leq n\)。

题解

https://blog.csdn.net/forever_dreams/article/details/99933598

min-max容斥+树上高消+高位前缀和，不错的签到题。

CO int N=18;
vector<int> to[N];
int a[N],b[N];
int f[1<<N];

void dfs(int u,int fa,int s){
    if(s>>u&1){
        a[u]=b[u]=0;
        return;
    }
    a[u]=b[u]=to[u].size();
    for(int v:to[u])if(v!=fa){
        dfs(v,u,s);
        a[u]=add(a[u],mod-a[v]);
        b[u]=add(b[u],b[v]);
    }
    a[u]=fpow(a[u],mod-2);
    b[u]=mul(b[u],a[u]);
}
int main(){
    int n=read<int>(),Q=read<int>(),x=read<int>()-1;
    for(int i=1;i<n;++i){
        int u=read<int>()-1,v=read<int>()-1;
        to[u].push_back(v),to[v].push_back(u);
    }
    for(int i=1;i<1<<n;++i){
        dfs(x,-1,i);
        f[i]=popcount(i)&1?b[x]:mod-b[x];
    }
    for(int i=0;i<n;++i)for(int j=0;j<1<<n;++j)
        if(j>>i&1) f[j]=add(f[j],f[j^(1<<i)]);
    while(Q--){
        int s=0;
        for(int k=read<int>();k--;) s|=1<<(read<int>()-1);
        printf("%d\n",f[s]);
    }
    return 0;
}

Topcoder RandomPaintingOnABoard 和 PKUWC2018 随机游走

原文：https://www.cnblogs.com/autoint/p/12129975.html