UOJ#348 州区划分

╰+哭是因爲堅強的太久メ 2021-12-22 16:49 231阅读 0赞

![1332167-20190417083635573-55319612.png][]

![1332167-20190417083708922-253576793.png][]

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

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

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

这枚举子集是3n的。

然后发现这是子集卷积，[参考资料][Link 1]。

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 
      3 typedef long long LL;
      4 const int N = 30, M = 2100000, MO = 998244353;
      5 
      6 struct Edge {
      7     int v, u;
      8 }edge[N * N];
      9 
     10 int w[N], sum[M], cnt[M], n, P, lm, invsum[M], pw[M], in[N], fa[N];
     11 int f[N][M], g[N][M];
     12 bool vis[M];
     13 
     14 int find(int x) {
     15     if(x == fa[x]) return x;
     16     return fa[x] = find(fa[x]);
     17 }
     18 
     19 inline void out(int x) {
     20     for(int i = 0; i < n; i++) {
     21         printf("%d", (x >> i) & 1);
     22     }
     23     return;
     24 }
     25 
     26 inline void merge(int x, int y) {
     27     fa[find(x)] = find(y);
     28     return;
     29 }
     30 
     31 inline int qpow(int a, int b) {
     32     int ans = 1;
     33     while(b) {
     34         if(b & 1) ans = 1ll * ans * a % MO;
     35         a = 1ll * a * a % MO;
     36         b = b >> 1;
     37     }
     38     return ans;
     39 }
     40 
     41 inline int pow(int x) {
     42     return P ? (P == 1 ? x : 1ll * x * x % MO) : 1;
     43 }
     44 
     45 inline void FWT_or(int *a, int n, int f) {
     46     for(int len = 1; len < n; len <<= 1) {
     47         for(int i = 0; i < n; i += (len << 1)) {
     48             for(int j = 0; j < len; j++) {
     49                 (a[i + len + j] += f * a[i + j]) %= MO;
     50                 if(a[i + len + j] < 0) a[i + len + j] += MO;
     51             }
     52         }
     53     }
     54     return;
     55 }
     56 
     57 int main() {
     58     int m;
     59     scanf("%d%d%d", &n, &m, &P);
     60 
     61     for(int i = 1, x, y; i <= m; i++) {
     62         scanf("%d%d", &edge[i].v, &edge[i].u);
     63     }
     64     for(int i = 1; i <= n; i++) scanf("%d", &w[i]);
     65     lm = (1 << n) - 1; /// lm = 1111111111(2)
     66     for(int i = 2; i <= lm; i++) pw[i] = pw[i >> 1] + 1;
     67     for(int s = 1; s <= lm; s++) {
     68         cnt[s] = cnt[s ^ (s & (-s))] + 1;
     69         vis[s] = 0;
     70         memset(in + 1, 0, n * sizeof(int));
     71         for(int i = 1; i <= n; i++) {
     72             fa[i] = i;
     73         }
     74         for(int i = 1; i <= m; i++) {
     75             if(((s >> (edge[i].v - 1)) & 1) && ((s >> (edge[i].u - 1)) & 1)) {
     76                 in[edge[i].v]++;
     77                 in[edge[i].u]++;
     78                 merge(edge[i].u, edge[i].v);
     79             }
     80         }
     81         bool nol = 0;
     82         int temp = 0;
     83         for(int i = 1; i <= n; i++) {
     84             if(in[i] & 1) {
     85                 vis[s] = 1;
     86             }
     87             if((s >> (i - 1)) & 1) {
     88                 (sum[s] += w[i]) %= MO;
     89                 if(!temp) {
     90                     temp = find(i);
     91                 }
     92                 else if(find(i) != temp) {
     93                     nol = 1;
     94                 }
     95             }
     96         }
     97         if(nol) vis[s] = 1;
     98         invsum[s] = qpow(sum[s], MO - 2);
     99         if(vis[s]) {
    100             g[cnt[s]][s] = pow(sum[s]);
    101         }
    102     }
    103 
    104     f[0][0] = 1;
    105     for(int i = 1; i <= n; i++) {
    106         FWT_or(g[i], lm + 1, 1);
    107     }
    108     FWT_or(f[0], lm + 1, 1);
    109     for(int i = 1; i <= n; i++) {
    110         for(int j = 1; j <= i; j++) {
    111             for(int s = 0; s <= lm; s++) {
    112                 (f[i][s] += 1ll * f[i - j][s] * g[j][s] % MO) %= MO;
    113             }
    114         }
    115         FWT_or(f[i], lm + 1, -1);
    116         for(int s = 0; s <= lm; s++) {
    117             f[i][s] = 1ll * f[i][s] * pow(invsum[s]) % MO;
    118         }
    119         if(i < n) FWT_or(f[i], lm + 1, 1);
    120     }
    121     printf("%d\n", f[n][lm]);
    122     return 0;
    123 }

AC代码

转载于:https://www.cnblogs.com/huyufeifei/p/10721352.html

[1332167-20190417083635573-55319612.png]: /images/20211220/134ce6552993420c814f67c7dade281d.png
[1332167-20190417083708922-253576793.png]: /images/20211220/e9101edaa95649b6afd01b57fbe35e18.png
[Link 1]: https://www.cnblogs.com/Khada-Jhin/p/10005488.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/c3aa581bb3fa42389bb11300cf260cc5.png