解题报告

搜FMT搜到这道题，其实我都想到怎么做了……结果以为自己解法是错的就没写了……

FMT除了集合并卷积之外还有一个经典应用就是子集卷积，他是这样的：

$$ h_s=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[A\cap B=\emptyset][A\cup B=s]f_Ag_B $$

就是在集合并卷积的基础上限制 $A,B$ 不能有交集，做法很暴力：由于 $[A\cap B=\emptyset][A\cup B=s]$ 等价于 $[|A|+|B|=|s|][A\cup B=s]$ ，所以在原来的基础上再记录一维长度，就可以直接用集合并卷积做了。

代码差不多长这样：

for (int i=0;i<=n;i++){
    FMT(f[i],n,1);FMT(g[i],n,1);
    for (int j=0;j<=i;j++) for (int s=0;s<S;s++) AMOD(h[i][s],(LL)f[j][s]*g[i-j][s]%MOD);
    FMT(h[i],n,-1);for (int s=0;s<S;s++) if (num[s]!=i) h[i][s]=0;FMT(h[i],n,1);
}

这道题就是选若干个没有交的集合组合成全集，所以写出式子：

$$ \begin{aligned} f_s&=\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[|A|+|B|=|s|][A\cup B=s]f_Ag_B{sum_B^P\over sum_s^P}\\ &={1\over sum_s^P}\sum_{A\subseteq2^U}\sum_{B\subseteq2^U}[|A|+|B|=|s|][A\cup B=s]f_Ag_Bsum_B^P \end{aligned} $$

其中 $g_s$ 表示 $s$ 这个集合是否有欧拉回路，$sum_s$ 表示 $s$ 这个集合的权值和。

我刚开始以为有 $1\over sum_s^P$ 做不了……实际上因为 $1\over sum_s^P$ 和 $A,B$ 无关所以可以做好卷积之后再算，这样的话直接用子集卷积就行了。最后答案为 $f_{n,U}$ 。

ps：欧拉回路记得判断不连通啊，我连这个都忘了啊，我要跪了啊QAQ。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=21,maxm=maxn*maxn,maxs=1<<maxn,MOD=998244353;

int n,S,m,P,a[maxn+5],num[maxs],sum[maxs],INV[maxs],p[maxn+5][maxs],f[maxn+5][maxs];
int E,lnk[maxn+5],son[maxm+5],nxt[maxm+5];
int que[maxn+5],ti,vis[maxn+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline bool check(int s){
    static int d[maxn+5];int now=0;for (int i=0;i<n;i++) d[i]=0;
    for (int i=0;i<n;i++) if (now+=s>>i&1,s>>i&1) for (int j=lnk[i];j;j=nxt[j]) s>>son[j]&1?d[i]++:0;
    for (int i=0;i<n;i++) if ((s>>i&1)&&(d[i]&1)) return true;
    int Head=0,Tail=0;for (int i=0;i<n;i++) if (s>>i&1) {que[++Tail]=i;vis[i]=++ti;break;}
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x];j;j=nxt[j])
            if ((s>>son[j]&1)&&vis[son[j]]<ti) que[++Tail]=son[j],vis[son[j]]=ti;
    if (Tail!=now) return true;return false;
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void FMT(int *a,int n,int f){
    for (int i=0;i<n;i++)
        for (int s=1<<i;s<(1<<n);s++)
            if (s>>i&1) AMOD(a[s],f>0?a[s^(1<<i)]:MOD-a[s^(1<<i)]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&P);S=1<<n;for (int s=1;s<S;s++) s&1?num[s]=num[s>>1]+1:num[s]=num[s>>1];
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),x--,y--,Add(x,y),Add(y,x);
    for (int i=0;i<n;i++) scanf("%d",&a[i]);for (int s=0;s<S;s++) for (int i=0;i<n;i++) s>>i&1?sum[s]+=a[i]:0;
    for (int s=0;s<S;s++) sum[s]=Pow(sum[s],P),INV[s]=Pow(sum[s],MOD-2),p[num[s]][s]=check(s)?sum[s]:0;
    for (int i=0;i<=n;i++){
        FMT(p[i],n,1);for (int s=0;s<S;s++) f[i][s]=p[i][s];
        for (int j=1;j<i;j++) for (int s=0;s<S;s++) AMOD(f[i][s],(LL)f[j][s]*p[i-j][s]%MOD);FMT(f[i],n,-1);
        for (int s=0;s<S;s++) num[s]!=i?f[i][s]=0:f[i][s]=(LL)f[i][s]*INV[s]%MOD;FMT(f[i],n,1);
    }FMT(f[n],n,-1);printf("%d\n",f[n][S-1]);return 0;
}