UOJ#348 州区划分

时间:2022-01-02 00:28:53

UOJ#348 州区划分

UOJ#348 州区划分

解:有一个很显然的状压......

就设f[s]表示选的点集为s的时候所有方案的权值和。

于是有f[s] = f[s \ t] * (sum[t] / sum[s])P

这枚举子集是3n的。

然后发现这是子集卷积,参考资料

于是就FWT搞一下...看代码

 #include <bits/stdc++.h>

 typedef long long LL;
const int N = , M = , MO = ; struct Edge {
int v, u;
}edge[N * N]; int w[N], sum[M], cnt[M], n, P, lm, invsum[M], pw[M], in[N], fa[N];
int f[N][M], g[N][M];
bool vis[M]; int find(int x) {
if(x == fa[x]) return x;
return fa[x] = find(fa[x]);
} inline void out(int x) {
for(int i = ; i < n; i++) {
printf("%d", (x >> i) & );
}
return;
} inline void merge(int x, int y) {
fa[find(x)] = find(y);
return;
} inline int qpow(int a, int b) {
int ans = ;
while(b) {
if(b & ) ans = 1ll * ans * a % MO;
a = 1ll * a * a % MO;
b = b >> ;
}
return ans;
} inline int pow(int x) {
return P ? (P == ? x : 1ll * x * x % MO) : ;
} inline void FWT_or(int *a, int n, int f) {
for(int len = ; len < n; len <<= ) {
for(int i = ; i < n; i += (len << )) {
for(int j = ; j < len; j++) {
(a[i + len + j] += f * a[i + j]) %= MO;
if(a[i + len + j] < ) a[i + len + j] += MO;
}
}
}
return;
} int main() {
int m;
scanf("%d%d%d", &n, &m, &P); for(int i = , x, y; i <= m; i++) {
scanf("%d%d", &edge[i].v, &edge[i].u);
}
for(int i = ; i <= n; i++) scanf("%d", &w[i]);
lm = ( << n) - ; /// lm = 1111111111(2)
for(int i = ; i <= lm; i++) pw[i] = pw[i >> ] + ;
for(int s = ; s <= lm; s++) {
cnt[s] = cnt[s ^ (s & (-s))] + ;
vis[s] = ;
memset(in + , , n * sizeof(int));
for(int i = ; i <= n; i++) {
fa[i] = i;
}
for(int i = ; i <= m; i++) {
if(((s >> (edge[i].v - )) & ) && ((s >> (edge[i].u - )) & )) {
in[edge[i].v]++;
in[edge[i].u]++;
merge(edge[i].u, edge[i].v);
}
}
bool nol = ;
int temp = ;
for(int i = ; i <= n; i++) {
if(in[i] & ) {
vis[s] = ;
}
if((s >> (i - )) & ) {
(sum[s] += w[i]) %= MO;
if(!temp) {
temp = find(i);
}
else if(find(i) != temp) {
nol = ;
}
}
}
if(nol) vis[s] = ;
invsum[s] = qpow(sum[s], MO - );
if(vis[s]) {
g[cnt[s]][s] = pow(sum[s]);
}
} f[][] = ;
for(int i = ; i <= n; i++) {
FWT_or(g[i], lm + , );
}
FWT_or(f[], lm + , );
for(int i = ; i <= n; i++) {
for(int j = ; j <= i; j++) {
for(int s = ; s <= lm; s++) {
(f[i][s] += 1ll * f[i - j][s] * g[j][s] % MO) %= MO;
}
}
FWT_or(f[i], lm + , -);
for(int s = ; s <= lm; s++) {
f[i][s] = 1ll * f[i][s] * pow(invsum[s]) % MO;
}
if(i < n) FWT_or(f[i], lm + , );
}
printf("%d\n", f[n][lm]);
return ;
}

AC代码

UOJ#348 州区划分的更多相关文章

  1. UOJ &num;348 州区划分 —— 状压DP&plus;子集卷积

    题目:http://uoj.ac/problem/348 一开始可以 3^n 子集DP,枚举一种状态的最后一个集合是什么来转移: 设 \( f[s] \) 表示 \( s \) 集合内的点都划分好了, ...

  2. &lbrack;UOJ&num;348&rsqb;&lbrack;WC2018&rsqb;州区划分

    [UOJ#348][WC2018]州区划分 试题描述 小 \(S\) 现在拥有 \(n\) 座城市,第ii座城市的人口为 \(w_i\),城市与城市之间可能有双向道路相连. 现在小 \(S\) 要将这 ...

  3. UOJ&num;348&period; 【WC2018】州区划分

    原文链接www.cnblogs.com/zhouzhendong/p/UOJ348.html 前言 第一次知道子集卷积可以自己卷自己. 题解 这是一道子集卷积模板题. 设 $sum[S]$ 表示点集 ...

  4. UOJ348&period; 【WC2018】州区划分

    UOJ348. [WC2018]州区划分 http://uoj.ac/problem/348 分析: 设\(g(S)=(\sum\limits_{x\in S}w_x)^p[合法]\) \(f(S)\ ...

  5. 【WC2018】州区划分(FWT,动态规划)

    [WC2018]州区划分(FWT,动态规划) 题面 UOJ 洛谷 题解 首先有一个暴力做法(就有\(50\)分了) 先\(O(2^nn^2)\)预处理出每个子集是否合法,然后设\(f[S]\)表示当前 ...

  6. &lbrack;WC2018&rsqb;州区划分——FWT&plus;DP&plus;FST

    题目链接: [WC2018]州区划分 题目大意:给n个点的一个无向图,点有点权,要求将这n个点划分成若干个部分,每部分合法当且仅当这部分中所有点之间的边不能构成欧拉回路.对于一种划分方案,第i个部分的 ...

  7. &lbrack;WC2018&rsqb;州区划分

    [WC2018]州区划分 注意审题: 1.有序选择 2.若干个州 3.贡献是州满意度的乘积 枚举最后一个州是哪一个,合法时候贡献sum[s]^p,否则贡献0 存在欧拉回路:每个点都是偶度数,且图连通( ...

  8. 「WC2018」州区划分(FWT)

    「WC2018」州区划分(FWT) 我去弄了一个升级版的博客主题,比以前好看多了.感谢 @Wider 不过我有阅读模式的话不知为何 \(\text{LATEX}\) 不能用,所以我就把这个功能删掉了. ...

  9. P4221 &lbrack;WC2018&rsqb;州区划分 无向图欧拉回路 FST FWT

    LINK:州区划分 把题目中四个条件进行规约 容易想到不合法当前仅当当前状态是一个无向图欧拉回路. 充要条件有两个 联通 每个点度数为偶数. 预处理出所有状态. 然后设\(f_i\)表示组成情况为i的 ...

随机推荐

  1. Linq to SQL 的增删改查操作

    Linq,全称Language Integrated Query,是C#语言的一个扩展,可以将数据查询直接集成到编程语言本身中. Linq分为查询语法和方法语法,说白了查询语法就是 from wher ...

  2. linux命令:mkdir 命令详解

    linux mkdir 命令用来创建指定的名称的目录,要求创建目录的用户在当前目录中具有写权限,并且指定的目录名不能是当前目录中已有的目录. 1.命令格式: mkdir [选项] 目录... 2.命令 ...

  3. ubuntu下怎么解决python &quot&semi;Non-ASCII character&quot&semi;错误

    解决方法:源代码文件第一行添加:#coding:utf-8 参考:  http://jingyan.baidu.com/album/219f4bf7d04887de442d3899.html?pici ...

  4. PS网页设计教程XXV——使用Photoshop设计的老式组合布局

    作为编码者,美工基础是偏弱的.我们可以参考一些成熟的网页PS教程,提高自身的设计能力.套用一句话,“熟读唐诗三百首,不会作诗也会吟”. 本系列的教程来源于网上的PS教程,都是国外的,全英文的.本人尝试 ...

  5. WDK编程的一些特殊点

    函数的多线程安全性在内核编程中比用户态应用程序的编程更常见. 调用源 运行环境 原因 driverEntry,DriverUnload 单线程 这两个函数由系统进程的单一线程调用,不会出现多线程同时调 ...

  6. 常用 Linux 命令

    Check page size: getconf PAGESIZE Check memory information: cat /proc/meminfo Check number of hugepa ...

  7. 转&colon;sublime text快捷键 (很实用的东东)

    一个好的编辑器,能大大提高编程的效率.如果能熟知软件的快捷键,那更能让你得心印手.这些内容都是我网上和自己实际使用过程中所收集而来的,在网络上应该也算比较全面的了吧.欢迎大家补充,我也会在以后慢慢添加 ...

  8. Oracle 查询表空间使用情况

    select *   from (Select a.tablespace_name,                to_char(a.bytes / 1024 / 1024, '99,999.999 ...

  9. Maven安装及配置

    第1部分 准备 1.1 安装JDK和Eclipse: 1.2 下载Maven(https://maven.apache.org/download.cgi) 第2部分 2.1 安装Maven 2.1.1 ...

  10. WEB UI基础八&colon;链接跳转到标准的工单界面

    接以前做的例子,用组件做了个搜索界面,明细里添加了object_id的链接: method GET_P_OBJECT_ID. "#EC NEEDED ** generated by sear ...