s2oj2046 GDKOI2023 Day1T3 异或图
好题，与 Ex - Distinct Multiples 类似，题解。
首先考虑没有边的情况，那么我们需要满足条件 \(1,3\)。
考虑从高位开始计算，设当前考虑到第 \(k\) 位，第 \(k\) 位前面的异或和与 \(C\) 第 \(k\) 位前面相同。可以发现如果至少有一个 \(b_i\) 满足这一位没有顶上界（即 \(b_i\) 的这一位为 \(0\) 且 \(a_i\) 这一位为 \(1\)），那么后面时其他的数 \(b_j(j\not=i)\) 可以随便选，因为 \(b_i\) 的低位可以随便选，一定能够恰好凑出 \(C\)。
那么只需要对于每一位算出有多少个 \(a_i=1\) 的数，那么要求选的个数与 \(C\) 的奇偶性相同。判断一下在奇偶性相同的前提下是否全选，若不全选则一定存在一个 \(b_i\) 没有顶上界。那么随便选一个没有顶上界的用来调整，其他的随便放即可。如果全选则放到下一位继续考虑。
此部分时间复杂度 \(\mathcal{O}(n \log C)\)。
考虑扩展到原问题，加入 \(b_u\not=b_v\) 的限制。假设我们已经钦定若干个 \(b_i\) 相同的部分，那么对于一个大小为奇数的连通块 \(s\)，其最小的元素存在贡献，即其可以看作一个点，其 \(a\) 值为 \(\min_{j\in s} a_j\)。对于一个大小为偶数的连通块 \(s\)，其没有贡献，但是有 \((\min_{j\in s}a_j)+1\) 种方案。
直接考虑容斥。简单的边集容斥已经在上面的题解中讲解，这里略去。考虑点集容斥。
依旧考虑将 \(n\) 个点划分为若干个连通块，则这种方案的容斥系数为所有连通块的系数之积。我们考虑其中一个连通块的容斥系数然后乘起来即可。由于这里图是给定的，所以顶点之间是有区别的，那就只能设 \(g_s\) 表示点集 \(s\) 的容斥系数，实际上是满足所有边的两个端点在 \(s\) 的点集中且使得 \(s\) 中点连通的边集的 \((-1)^{|e|}\) 之和，其中 \(|e|\) 为边集大小。
容斥计算使得 \(s\) 不连通的边集的系数之和，令 \(\mu(s)\) 在原图中点集 \(s\) 内部存在边时为 \(0\)，否则为 \(1\)。那么可以得到总系数为 \(\sum_{j=0}^{|e|}\binom{|e|}{j}(-1)^j=[|e|=0]=\mu(s)\)。
\[g_s=\mu(s)-\sum_{t\subseteq s,\text{low}_s=\text{low}_t}g_t\mu(s-t) \]直接暴力枚举子集即可得到容斥系数。注意：转移时需要钦定 \(s\) 中的最小元素相同。
我们发现对于一种划分来说，我们只关心每个连通块 \(s\) 中的 \(\min_{j\in s} a_j\)，即 \(a_j\) 最小的位置，考虑在 \(\text{dp}\) 的时候记录下来。
设 \(f_{s,t}\) 表示当前已经考虑了集合 \(s\) 的点，作为奇数连通块中的 \(\min\) 出现的 \(a_j\) 的 \(j\) 的集合为 \(t\) 的容斥系数乘上偶数连通块贡献的和。
那么转移的时候分奇偶性连通块的奇偶性讨论，若为偶数直接乘上贡献，若为奇数在 \(t\) 中更新即可（注意：依然需要钦定 \(s\) 中最小的元素必选）。由于状态量不会很大，使用 unordered_map 存储即可。
时间复杂度 \(\mathcal{O}(能过)\)。
code
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 20
#define ll long long
#define p 998244353
inline int add(int x,int y){
return x+y>=p?x+y-p:x+y;
}
inline int mul(int x,int y){
return (long long)x*y%p;
}
inline int power(int x,int y){
int res=1;
while(y){
if(y&1) res=mul(res,x);
x=mul(x,x),y>>=1;
}
return res;
}
int fac[N],inv[N],pw[N<<2],ipw[N<<2],pre[2],now[2];
ll w[N],val[N],k;
inline int calc(int n){
int res=0;
for(int b=60;~b;b--){
now[0]=1,now[1]=0;
int num=0,c=k>>b&1,res0=1;
for(int i=1;i<=n;i++){
pre[0]=now[0],pre[1]=now[1],num+=val[i]>>b&1;
if(val[i]>>b&1){
now[0]=add(mul(pw[b],pre[1]),mul((val[i]&((1ll<<b)-1))%p+1,pre[0]));
now[1]=add(mul(pw[b],pre[0]),mul((val[i]&((1ll<<b)-1))%p+1,pre[1]));
}else{
now[0]=mul(pre[0],(val[i]&((1ll<<b)-1))%p+1);
now[1]=mul(pre[1],(val[i]&((1ll<<b)-1))%p+1);
}
res0=mul(res0,(val[i]&((1ll<<b)-1))%p+1);
}
now[0]=add(now[0],p-res0);
if(num) res=add(res,mul(now[c^(num&1)],ipw[b]));
if((num&1)!=c) break;
if(!b) res=add(res,1);
}
return res;
}
int n,m,c[N],ed[N],g[1<<15],minpos[1<<15],low[1<<15],ans,E[1<<15];
unordered_map<int,int> f[1<<15];
signed main(){
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
read(n,m,k),pw[0]=ipw[0]=1;
for(int i=1;i<=60;i++) pw[i]=add(pw[i-1],pw[i-1]),ipw[i]=power(pw[i],p-2);
for(int i=1;i<=n;i++) read(w[i]);
for(int i=1,u,v;i<=m;i++)
read(u,v),ed[u]|=(1<<v-1),ed[v]|=(1<<u-1);
for(int s=1;s<(1<<n);s++){
low[s]=(s&1)?1:low[s>>1]+1;
for(int i=1;i<=n;i++)
if(s>>(i-1)&1) E[s]+=__builtin_popcount(s&ed[i]);
if((s&-s)==s) minpos[s]=low[s];
else minpos[s]=(w[minpos[s^(s&-s)]]<w[low[s]])?minpos[s^(s&-s)]:low[s];
}
for(int s=1;s<(1<<n);s++){
g[s]=!E[s];
for(int t=(s-1)&s;t;t=(t-1)&s)
if(low[s]==low[t]&&!E[s^t]) g[s]=add(g[s],p-g[t]);
}
f[0][0]=1;
for(int s=0;s<(1<<n);s++)
for(auto t:f[s])
for(int L=((1<<n)-1)^s,S=L;S;S=(S-1)&L)
if(low[L]==low[S]){
int dis=(__builtin_popcount(S)&1)?1:(w[minpos[S]]%p+1),T=(__builtin_popcount(S)&1)?(t.first|(1<<minpos[S]-1)):t.first;
f[s|S][T]=add(f[s|S][T],mul(t.second,mul(dis,g[S])));
}
for(auto t:f[(1<<n)-1]){
if(!t.second) continue;
int num=0;
for(int i=1;i<=n;i++)
if(t.first>>(i-1)&1) val[++num]=w[i];
ans=add(ans,mul(t.second,calc(num)));
}
put('\n',ans);
return 0;
}