子集卷积谁知道题呀|[WC2018]州区划分（子集卷积）
【子集卷积谁知道题呀|[WC2018]州区划分（子集卷积）】传送门
首先我们可以列个dp方程出来：
dpS=(1wS)p∑T?SdpT?(wS?T)pd p S = ( 1 w S ) p ∑ T ? S d p T ? ( w S ? T ) p
然后这样枚举子集暴力dp是 O(3n)O ( 3 n ) 的
然后我们可以加一维变成子集卷积 dpi,Sd p i , S
然后直接子集卷积做就好了
O(n22n)O ( n 2 2 n )
这题不知道是卡常数还是我写的丑，反正就是最慢的点14s
顺带一提，这个题我还试了试刚刚学的FMT，看代码常数挺小，可是我还是这么慢qwq
代码：
#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=' ';
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
const int N=1<<21,mod=998244353;
int n,m,p,tot,L;
int head[N],to[N],Next[N];
int deg[N],fa[N],v[N],can[N];
int w[N],inv[N],dp[22][N],g[22][N];
inline void addedge(int x,int y){to[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline LL ksm(LL a,LL n){
LL ans=1LL;
while(n){
if(n&1)ans=ans*a%mod;
a=a*a%mod;
n>>=1;
}
return ans;
}
inline bool check(int S){
int cnt=0;
for(int i=0;
i>i)&1)fa[i]=i,++cnt,deg[i]=0,w[S]+=v[i];
for(int i=0;
i>i)&1))continue;
for(int j=head[i];
j;
j=Next[j]){
int u=to[j];
if(!((S>>u)&1))continue;
++deg[i];
++deg[u];
int fi=find(i),fu=find(u);
if(fi!=fu)fa[fi]=fu,--cnt;
}
}
if(cnt>1)return true;
cnt=0;
for(int i=0;
i>i)&1) && (deg[i]&1))++cnt;
if(cnt==0)return false;
return true;
}
inline LL calc(LL x){
if(!p)return 1;
else if(p==1)return x%mod;
else return x*x%mod;
}inline void FMT(int *a){
for(int i=1;
i>i)&1)++cnt;
if(can[k])g[cnt][k]=w[k];
inv[k]=ksm(w[k],mod-2);
}
dp[0][0]=1;
FMT(dp[0]);
for(int i=0;
i<=n;
++i)FMT(g[i]);
for(int i=1;
i<=n;
++i){
for(int j=0;
j 推荐阅读
- 宽容谁
- 在古城迷惑如何觅食吗（看这里！）
- 谁还用剩米饭做蛋炒饭啊，现在流行这么吃！
- 无论你是谁，都有两件事，无法掌控
- 谁还顾念小城的旧（）
- 拜托
- 绘本讲师训练营【28期】19/21阅读原创《谁下了最美丽的蛋》
- 那个谁，你别跑啊！！
- 八千里路云和月（九）究竟十八年前是谁邮寄的明信片
- 绘本讲师训练营【26期】20/21|绘本讲师训练营【26期】20/21 阅读原创—《是谁嗯嗯在我的头上》