Description 题面到处都有系列。。
Solution FMT是啥，能吃吗
首先考虑怎么判合法子图（也就是欧拉回路），我们n2*2n枚举点然后统计度数就可以了
那么一个比较显然的dp就是设f[S]表示二进制状态为S的所有答案,g[S]表示S这个集合分成一份的贡献
我们枚举S的子集转移即可，这样做是O(3n)的
【c++|loj2340 WC2018 州区划分 状压dp+FWT】考虑把柿子写出来，那么就是 f S = ∑ T ? S f T ? g S ? T f_{S}=\sum\limits_{T\subset S}f_{T}\cdot g_{S\setminus T} fS?=T?S∑?fT??gS?T?
这实际上就是一个子集卷积，只不过这个有自己卷自己的部分。
注意到 ∑ T ? S f T ? g S ? T = ∑ U ? S , V ? S , U ∪ V = S , U ∩ V = ? f U ? g V = ∑ U ? S , V ? S , ∣ U ∣ + ∣ V ∣ = ∣ S ∣ , U ∪ V = S f U ? g V \sum\limits_{T\subset S}{f_{T}\cdot g_{S\setminus T}}=\sum\limits_{U\subset S,V\subset S,U\cup V=S,U\cap V=\emptyset}{f_{U}\cdot g_{V}}=\sum\limits_{U\subset S,V\subset S,|U|+|V|=|S|,U\cup V=S}f_{U}\cdot g_{V} T?S∑?fT??gS?T?=U?S,V?S,U∪V=S,U∩V=?∑?fU??gV?=U?S,V?S,∣U∣+∣V∣=∣S∣,U∪V=S∑?fU??gV?
这里的转化十分的巧妙
于是我们设 f i , S f_{i,S} fi,S?表示二进制中i位是1，状态为S的答案，我们对i做卷积，然后对S做或卷积就可以了
于是复杂度就是 O ( n 2 ? 2 n ) O(n^2\cdot2^n) O(n2?2n)的了，我写的代码要卡一卡常数。。
Code
#include
#include
#include
#define rep(i,st,ed) for (register int i=st;
i<=ed;
++i)typedef long long LL;
const int MOD=998244353;
const int N=2197152;
LL f[22][N],g[22][N],s[N],inv[N];
int rc[22][22],fa[22],d[22],w[22],c[N];
int n,m,p,lim;
void upd(LL &x,LL y) {
x+=y;
(x>=MOD)?(x-=MOD):0;
}int read() {
int x=0,v=1;
char ch=getchar();
for (;
ch<'0'||ch>'9';
v=(ch=='-')?(-1):(v),ch=getchar());
for (;
ch<='9'&&ch>='0';
x=x*10+ch-'0',ch=getchar());
return x*v;
}void FWT(LL *a,int f) {
for (register int i=1;
i>=1) {
(dep&1)?(res=res*x%MOD):0;
x=x*x%MOD;
}
return res;
}int find(int x) {
return !fa[x]?x:(fa[x]=find(fa[x]));
}bool merge(int x,int y) {
x=find(x),y=find(y);
if (x==y) return false;
return 1|(fa[x]=y);
}bool check(int S) {
rep(i,1,n) fa[i]=d[i]=0;
int cnt=1;
rep(i,1,n) if (S>>(i-1)&1) {
s[S]=(s[S]+w[i])%MOD;
rep(j,i+1,n) if (S>>(j-1)&1) {
if (!rc[i][j]) continue;
++d[i],++d[j];
cnt+=merge(i,j);
}
}
inv[S]=ksm(ksm(s[S],MOD-2),p);
rep(i,1,n) if (S>>(i-1)&1) {
if (d[i]&1) return false;
cnt--;
}
return !cnt;
}int main(void) {
freopen("data.in","r",stdin);
freopen("myp.out","w",stdout);
n=read(),m=read(),p=read();
lim=(1<>1]+(i&1);
rep(i,1,lim) if (!check(i)) {
// printf("%d\n", i);
g[c[i]][i]=ksm(s[i],p);
}
f[0][0]=1;
rep(i,0,n-1) f[1][1< 推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题