题目链接: [WC2018]州区划分 题目大意:给n个点的一个无向图,点有点权,要求将这n个点划分成若干个部分,每部分合法当且仅当这部分中所有点之间的边不能构成欧拉回路.对于一种划分方案,第i个部分的权值为这一部分中所有点的权值和比上前i部分所有点的权值和的p次方,一种划分方案的权值为每部分的权值之积.要求求出所有划分方案的权值之和. 我们设f[S]为选中点的状态集合为S时的答案(其中S为二进制状态),设T为S集合最后一次划分出的集合且要保证集合T合法,那么可以得到转移方程(其中sum代表集合中

[WC2018]州区划分 注意审题: 1.有序选择 2.若干个州 3.贡献是州满意度的乘积 枚举最后一个州是哪一个,合法时候贡献sum[s]^p,否则贡献0 存在欧拉回路:每个点都是偶度数,且图连通(dfs验证) 然后愉快子集卷积即可. PS:FMT辣鸡, FWT可以节省一倍的常数!这样才能通过此题 #include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se sec

[UOJ#348][WC2018]州区划分 试题描述 小 \(S\) 现在拥有 \(n\) 座城市,第ii座城市的人口为 \(w_i\),城市与城市之间可能有双向道路相连. 现在小 \(S\) 要将这 \(n\) 座城市划分成若干个州,每个州由至少一个城市组成,每个城市在恰好一个州内. 假设小 \(S\) 将这些城市划分成了 \(k\) 个州,设 \(V_i\) 是第 \(i\) 个州包含的所有城市组成的集合. 定义一条道路是一个州的内部道路,当且仅当这条道路的两个端点城市都在这个州内. 如果一

[WC2018]州区划分(FWT,FST) Luogu loj 题解时间 经典FST. 在此之前似乎用到FST的题并不多? 首先预处理一个子集是不是欧拉回路很简单,判断是否连通且度数均为偶数即可. 考虑朴素状压dp很容易得到 $ f_{ S } = \sum\limits_{ T \subseteq S } f_{ S - T } \times ( \frac{ val_{ T } }{ val_{ S } } )^{p} $ . 直接dp时间复杂度 $ 3^{ N } $ 当场去世. 但由于是

LINK:州区划分 把题目中四个条件进行规约 容易想到不合法当前仅当当前状态是一个无向图欧拉回路. 充要条件有两个 联通 每个点度数为偶数. 预处理出所有状态. 然后设\(f_i\)表示组成情况为i的值. 枚举子集转移 可以发现利用FST进行优化. FST怎么做?详见另一篇文章史上最详细FST解释 code //#include<bits/stdc++.h> #include<iostream> #include<cstdio> #include<ctime>

题目描述 题解 这道题的思路感觉很妙. 题目中有一个很奇怪的不合法条件,貌似和后面做题没有什么关系,所以我们先得搞掉它. 也就是判断一个点集是否合法,也就是判断这个点集是否存在欧拉回路. 如果存在欧拉回路每个点的度都得是偶数而且图联通,这个条件扫描一遍在上一个并查集就可以判掉了. 然后开始统计答案. n很小,可以考虑状压dp,我们设dp[s]为已经划分好的州区点集和为s它的所有方案的答案的和. 转移可以考虑枚举子集. dp[s]=∑dp[s']*(sum[s^s']/sum[s])p 然后我们发

合法条件为所有划分出的子图均不存在欧拉回路或不连通,也即至少存在一个度数为奇数的点或不连通.显然可以对每个点集预处理是否合法,然后就不用管这个奇怪的条件了. 考虑状压dp.设f[S]为S集合所有划分方案的满意度之和,枚举子集转移,则有f[S]=Σg[S']*f[S^S']*(sum[S']/sum[S])p (S'⊆S),其中g[S]为S集合是否合法,sum[S]为S集合人口数之和.复杂度O(3n).这个式子非常显然,就这么送了50分.p这么小显得非常奇怪但也没有任何卵用. 考虑优化.转移方程写

题目链接 正解:子集和变换. 考场上只会暴力和$p=0$的情况,还只会$O(2^{n}*n^{3})$的. 然而这题题面出锅,导致考场上一直在卡裸暴力,后面的部分分没写了..听$laofu$说$O(2^{n}*n^{3})$可以过.. 所以直接讲正解.. 我们假设每个城市可以在两个不同集合,那么可以把子集卷积变成或卷积. 我们只要记下当前总共有多少个点,于是考虑设$f[i][S]$表示$i$个点,集合为$S$的方案数. 最后的$f[n][all]$就是答案,显然这个状态中的每个城市只会出现一次.

题目链接 洛谷题面. LOJ题面.还是LOJ机子比较快 Solution 设\(f(s)\)表示选\(s\)这些城市的总代价,那么我们可以得到一个比较显然的\(dp\): \[ f(s)=\frac{1}{sum_s^p}\sum_{t\subset s} f(t)g(s-t) \] 其中\(g(i)\)表示合法的\(sum_i^p\),即若不合法则为\(0\). 这个\(dp\)是\(O(3^n)\)的,注意到这是个子集卷积的形式,我们可以考虑用\(fwt\)优化它. 那么我们可以一层一层的\

传送门(uoj) 传送门(洛谷) 全世界都会子集卷积就咱不会--全世界都在写\(FMT\)就咱只会\(FWT\)-- 前置芝士 或运算\(FWT\)或者\(FMT\) 左转洛谷模板区,包教包会 子集卷积 定义:对于两个集合幂级数\(F,G\),它们的子集卷积\(H\)定义为\[H_S=\sum_{T\subseteq S}F_TG_{S-T}\] 简单来说就是两个下标要满足的条件为\(L\cap R=\varnothing\)且\(L\cup R=S\) \(L\cup R=S\)就是个异或卷积

题目链接 题目描述 略 Sol 一个州合法就是州内点形成的子图中 不存在欧拉回路(一个点也算欧拉回路). 这个东西显然就状压 dp 一下: 设 \(f[S]\) 表示当前考虑了 \(S\) 这个集合内所有点的所有方案满意度之和. 转移就枚举一个子集作为最后选出的一个州 \[f[S]=\bigg(\frac{1}{sum[S]}\bigg)^p\sum_{T\subseteq S}f[T]*g[S-T]\] \(sum[S]\) 表示 \(S\) 内所有城市的人口之和 \(g[S]\) 表示 ,

[洛谷题面]https://www.luogu.org/problemnew/show/P4221 首先考虑判定一个子图是否合法: (1)连通:并查集判断即可. (2)没有欧拉回路:存在欧拉回路的条件是度数均为偶数,计算度数判断即可. 容易想到进行状压DP,设 \(F[S]\) 表示选取点集 \(S\) 的答案. \[F[S]=\frac{1}{SumW(S)} \sum_{T\subseteq S} F[S-T]*SumW(T)\] 直接按上式暴力,复杂度为 \(O(3^n)\),可以通过 \

题目分析: 这题是WC的题??? 令 $g[S] = (\sum_{x \in S}w_x)^p$ $h[S] = g[S]$如果$S$不是欧拉回路 $d[S] = \frac{f[S]}{g[All-S]^p}$ $f[S] = \sum_{T \subset S}d[S-T]*h[T]$ 总数等于$f[All]$ 代码: #include<bits/stdc++.h> using namespace std; ; ; <<)+],g[(<<)+],d[maxn][(

很裸的子集反演模板题,套上一些莫名其妙的外衣. 先预处理每个集合是否合法,再作显然的状压DP.然后发现可以写成子集反演的形式,直接套模板即可. 子集反演可以看这里. 子集反演的过程就是多设一维代表集合大小,再FMT处理集合并卷积. 然而我的FMT常数过大,而并卷积又可以用FWT实现,于是就写FWT了.(实际上就三行的区别) #include<cstdio> #include<algorithm> #include<cstring> #define rep(i,l,r)

传送门 应该都会判欧拉回路吧(雾 考虑状压DP:设\(W_i\)表示集合\(i\)的点的权值和,\(route_i\)表示点集\(i\)的导出子图中是否存在欧拉回路,\(f_i\)表示前若干个城市包含了集合\(i\)的所有方案满意度的和,转移枚举最后一个放入的城市集合\(x\),有\(f_i = \frac{\sum\limits_{x \subset i} [route_x] W_x \times f_{i \oplus x}}{W_i}\). 可以注意到两个不交的状态\(i,j\)可以转移到

[WC2018]州区划分(FWT,动态规划) 题面 UOJ 洛谷 题解 首先有一个暴力做法(就有\(50\)分了) 先\(O(2^nn^2)\)预处理出每个子集是否合法,然后设\(f[S]\)表示当前的答案,每次枚举一个子集进行转移,得到方程:\(\displaystyle f[S]=(\frac{1}{W_s})^p\sum_{T\subset S}f[T]*(W_{S-T})^p*check[S-T]\). 其中\(W\)表示权值和,\(check\)表示是否合法. 这样子的复杂度是\(O(

「WC2018」州区划分(FWT) 我去弄了一个升级版的博客主题,比以前好看多了.感谢 @Wider 不过我有阅读模式的话不知为何 \(\text{LATEX}\) 不能用,所以我就把这个功能删掉了. 洛谷上不开 \(O_2\) 根本过不去,自带大常数被卡到 \(15\) 分... 首先题了读了很久,发现一个州的集合可以不连通... 我们可以 \(O(n^22^n)\) 检验每一个状态是否满足条件,用并查集即可. \(f[S]\) 为状态 \(S\) 时的满意度之和,\(g[S]\) 当状态 \

UOJ348. [WC2018]州区划分 http://uoj.ac/problem/348 分析: 设\(g(S)=(\sum\limits_{x\in S}w_x)^p[合法]\) \(f(S)\)表示\(S\)集合内的答案. \(f(S)=\sum\limits_{T\subseteq S,|T|>0}g(T)f(S-T)s(S)\). 这玩意可以使用占位多项式搞搞. 大概就是形如\(f(S)=\sum\limits_{P|Q=S,|P|+|Q|=S}g(P)h(Q)\). 多开一维表示\

原文链接www.cnblogs.com/zhouzhendong/p/UOJ348.html 前言 第一次知道子集卷积可以自己卷自己. 题解 这是一道子集卷积模板题. 设 $sum[S]$ 表示点集 S 的点权和. 设 $f[S]$ 表示对点集 S 进行州区划分得到的答案,定义 $g[S]$ 在点集 S 合法时为 $(sum[S])^p$,不合法时为 0 . 则 $$f[S] = \frac{1}{(sum[S])^p}\sum_{T\subsetneq S} f[T]g[S-T]$$ 这东西是

题目大意 给定一个\(n\)个点的无向图,对于每种 \(n\) 个点的划分\(\{S_1,S_2,\ldots,S_k\}\),定义它是合法的,当且仅当每个点都在其中的一个集合中且对于任何的\(i\in[1,k]\),点集\(S_i\)非空,且导出子图不存在欧拉回路. 给定数组\(w_i\),求对于所有合法的划分\(\{s_1,s_2,\ldots,s_k\}\),下面的式子之和 \[ {(\prod_{i=1}^k\frac{\sum_{x\in S_i}w_x}{\sum_{j=1}^i\s