JZOJ5957. 【NOIP2018模拟11.7A组】scarborough fair
题意:
数据范围:
对于 % 的数据,满足 。
对于另外 % 的数据,满足 。
对于 % 的数据 (包括以上 % 的数据),满足 。
对于 % 的数据,满足 。
时限。
Analysis:
肯定是个状压DP。
发现点的数量其实不多,那么我们可以枚举联通块算贡献,因为期望=概率*权值。
我们枚举一个点集,使其成为联通块,且为保证不算重,此联通块一定不能再扩张,即向外的连边全部除掉。那么其它边可以任意连,外面的概率就为。我们要算出一个点集自成联通块的概率。
发现直接算不好算,考虑用总的减去不合法的,总概率显然为。设表示点集自成联通块的概率。那么我们枚举编号最小的点所在的联通块(这样不会算重,很经典的套路),然后因为要使其和剩下的点不连通,然后剩下的点之间可以任意连(概率就为)。
这就是一个枚举子集,发现我们还需要算跨越两个点集的边的概率乘积。
我们考虑处理出一个表示,点集互相的连边的乘积。那么若要跨越两个点集:。
我们就可以用除掉它们内部的边,即。此题就解决了。
复杂度。
Code:
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std;
# define low(x) ((x) & (-x))
const int N = 17 + 5;
const int M = 1 << 17;
const int mo = 998244353;
typedef long long ll;
int p[N][N],e[M][2],t[M];
int n,m,ans;
inline int pow(int x,int p)
{
int ret = 1;
for (; p ; p >>= 1,x = (ll)x * x % mo)
if (p & 1) ret = (ll)ret * x % mo;
return ret;
}
inline int dec(int x,int y) { return x - y < 0 ? x - y + mo : x - y; }
inline int inc(int x,int y) { return x + y >= mo ? x + y - mo : x + y; }
int main()
{
freopen("fair.in","r",stdin);
freopen("fair.out","w",stdout);
scanf("%d%d",&n,&m); int lim = 1 << n;
for (int i = 1 ; i <= m ; ++i)
{
int u,v; scanf("%d%d",&u,&v);
scanf("%d",&p[u][v]),p[v][u] = p[u][v];
}
for (int i = 0 ; i < lim ; ++i)
{
e[i][0] = 1;
for (int j = 0 ; j < n ; ++j)
if (i & (1 << j))
for (int k = j + 1 ; k < n ; ++k)
if ((i & (1 << k)) && p[j + 1][k + 1]) e[i][0] = (ll)e[i][0] * p[j + 1][k + 1] % mo;
e[i][1] = pow(e[i][0],mo - 2);
}
for (int i = 0 ; i < n ; ++i) t[1 << i] = 1;
for (int i = 2 ; i < lim ; ++i)
{
if (i == low(i)) continue;
int pos = low(i),x = i - pos; t[i] = 1;
for (int nx = (x - 1) & x ; ; nx = (nx - 1) & x)
{
int now = i ^ (nx | pos);
t[i] = dec(t[i],(ll)t[nx | pos] * e[i][0] % mo * e[nx | pos][1] % mo * e[now][1] % mo);
if (!nx) break;
}
}
for (int i = 1 ; i < lim ; ++i) ans = inc(ans,(ll)t[i] * e[lim - 1][0] % mo * e[i][1] % mo * e[(lim - 1) ^ i][1] % mo);
printf("%d\n",ans);
return 0;
}