Endless Pallet(min-max容斥)

分析：

设$x_i$表示第i个点被染成黑色的时间，所求即为$E(max \left \{x_i \right \})$

因为$E(X)=\sum_{k=1}^{\infty}i \times P(X=k)=\sum_{k=1}^{\infty}P(X\geqslant k)$，所以即求$\sum_{k=1}^{\infty}P(max\left \{ x_i \right \}\geqslant k)$

我们来考虑$P(max\left \{ x_i \right \}\geqslant k)$如何求

$P(max\left \{ x_i \right \}\geqslant k)=1-P(max\left \{ x_i \right \}< k)$

$P(max\left \{ x_i \right \}< k)=P(x_1<k,x_2<k,...,x_n<k)=\sum_{T \subseteq X}(-1)^{|T|}P(t_1\geqslant k,t_2 \geqslant k,...,t_{ |T|} \geqslant k )$

其中后面一部分是容斥原理

那么我们可以暴力枚举子集，算后面的那一坨的概率

假设固定了T，那么我们计算出从$\frac{n(n+1)}{2}$个染色方案中可以选取A个，使得没有包含T中任何一个元素

那么后面那一坨的概率就是$(\frac{2 \times A}{n(n+1)})^{k-1}$

我们发现，当我们枚举$k=1,2,...,\infty $的时候，这是一个等比数列，所以对答案的贡献是$\frac{1}{1-(\frac{2 \times A}{n(n+1)})}$

注意，当$A=\frac{n(n+1)}{2}$的时候，是不成立的，因为不是等比数列，这种情况下对于每一个k，这一项的贡献都是1，正好与$P(max\left \{ x_i \right \}\geqslant k)=1-P(max\left \{ x_i \right \}< k)$里面的1相抵消

于是我们得到了一个最终的式子：$\sum_{k=1}^{\infty}P(max\left \{ x_i \right \}\geqslant k)=\sum_{T \subseteq X,T\neq \varnothing }(-1)^{|T|+1}\frac{1}{1-(\frac{2 \times A_T}{n(n+1)})}$

其中$A_T$是子集T对应的A

我们需要想办法优化这个指数级别的算法，注意到对答案有影响的只有$A$和$|T|$，我们可以考虑用树形dp计算出有同样的A和|T|的有多少个集合

考虑一个子问题：给你一个树，有一些点是关键点，你需要统计出有多少条链不经过其中任何一个关键点

这个问题是可以树形dp解决的，状态需要保存以u为根的子树中，与u连通的非关键点形成的连通块的大小

于是对于我们这个问题，我们设$dp[i][j][A][0/1]$表示以i为根的子树，与i相连的没被选入点集的连通块大小为j，已经有了A条不经过点集中点的链，选取的点的数量的奇偶性是0/1情况下的点集有多少个

然后就可以对于dp出的值算贡献了

这个dp看似是$O(n^7)$的，但是它实际的复杂度是$O(n^5)$，原因与广外人知的树形背包的复杂度分析相同。(tip：不妨考虑我现在有n个数字1，每次需要把两个数字相加合成新的数字，代价是两个数字的乘积。问我最终合并成1个n，最少要花费多少代价。这个问题的答案是固定的，答案是$O(n^2)$级别的，这个问题等价于基于子树大小的树背包，所以树背包的复杂度是$O(n^2)$而不是$O(n^3)$)。

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 const int mod=;

 int dp[maxn+][maxn+][][];

 int tmp[maxn+][][];

 int inv[maxn*maxn+];

 int sz[maxn+];

 vector<int> g[maxn+];

 int n;

 int mul(int a,int b)

 {

     return 1LL*a*b%mod;

 }

 int add(int a,int b)

 {

     return (a+b)%mod;

 }

 void merge(int a[maxn+][][],int b[maxn+][][],int n,int m)

 {

     for(int i=;i<=n+m;++i)

         for(int j=;j<=(n+m)*(n+m+)/;++j)

             tmp[i][j][]=tmp[i][j][]=;

     for(int i=;i<=n;++i)

         for(int j=;j<=n*(n+)/;++j)

             for(int k=;k<;++k)

                 if(a[i][j][k])

                     for(int x=;x<=m;++x)

                         for(int y=;y<=m*(m+)/;++y)

                             for(int z=;z<;++z)

                                 if(b[x][y][z])

                                     tmp[i?i+x:][j+y+i*x][k^z]=add(tmp[i?i+x:][j+y+i*x][k^z],mul(a[i][j][k],b[x][y][z]));

     for(int i=;i<=n+m;++i)

         for(int j=;j<=(n+m)*(n+m+)/;++j)

             for(int k=;k<;++k)

                 a[i][j][k]=tmp[i][j][k];

 }

 void dfs(int k,int fa)

 {

     sz[k]=;

     dp[k][][][]=;

     dp[k][][][]=;

     for(auto u:g[k])

     {

         if(u==fa) continue;

         dfs(u,k);

         merge(dp[k],dp[u],sz[k],sz[u]);

         sz[k]+=sz[u];

     }

 }

 int main()

 {

     inv[]=;

     for(int i=;i<=*(+)/;++i) inv[i]=mul(mod-mod/i,inv[mod%i]);

     int T;

     scanf("%d",&T);

     for(int cas=;cas<=T;++cas)

     {

         printf("Case #%d: ",cas);

         scanf("%d",&n);

         for(int i=;i<=n;++i) g[i].clear();

         for(int i=;i<=n;++i)

             for(int j=;j<=n;++j)

                 for(int k=;k<=n*(n+)/;++k)

                     for(int l=;l<;++l)

                         dp[i][j][k][l]=;

         for(int i=;i<n;++i)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             g[u].push_back(v);

             g[v].push_back(u);

         }

         dfs(,);

         int ans=;

         int s=n*(n+)/;

         for(int i=;i<=n;++i)

             for(int j=;j<s;++j)

                 for(int k=;k<;++k)

                 {

                     int tmp=mul(s,inv[s-j]);

                     tmp=mul(tmp,dp[][i][j][k]);

                     if(k==) tmp=-tmp;

                     ans=add(ans,tmp);

                 }

         if(ans<) ans+=mod;

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

Endless Pallet(min-max容斥)

最新文章

热门文章