【CF1119H】Triple
Description
给出\(n\)个三元组\(a_i,b_i,c_i\)，范围为\([0,2^m-1]\)
再给出参数\(x,y,z\)，每个三元组有\(x\)个\(a_i\)，\(y\)个\(b_i\)，\(z\)个\(c_i\)
对于所有\(x\in[0,2^m-1]\)，从每个三元组中选一个数，求异或和为\(x\)的方案数
模\(998244353\)
Input
一行两个数\(n,m\)
然后一行三个\(x,y,z\)
然后\(n\)行读入三元组
Output
一共\(2^m\)个数表示答案
Sample Input
1 1
1 2 3
1 0 1
Sample Output
2 4
Data Constraint
\(1\le n\le 10^5,1\le k\le 17\)
Solution
典题
不妨直接做更加一般的情况
假设有\(k\)种数（本题就是\(3\)）
考虑原先的做法，枚举一个位置\(p\)，求算所有情况的系数\(c_k\)
其中\(k\)的第\(j\)位为\(1\)则表示\(popcount(p\&a_{i,k})=1\)，否则为\(0\)
我们可以列出\(2^k\)个线性无关的方程来求解所有的\(c\)
于是可以想到枚举一个\(T\)，令\(w_i=\oplus_{j\in T}a_{i,j}\)，然后得到集合幂级数\(f_T=\sum_{i=1}^nx^{w_i}\)
对\(f\)再做一次FWT，可以发现\([x^p]F_T=\sum_{i=1}^n(-1)^{popcount(p\&w_i)}=\sum_{i=1}^n\prod_{j\in T}(-1)^{popcount(p\&a_{i,j})}\)
观察\(c\)对\(F\)的贡献
显然，只有\(T\)中的位是能产生贡献的
由定义，这个系数恰好就是\((-1)^{popcount(T\&k)}\)
于是\([x^p]F_T=\sum_{i=0}^{2^k-1}(-1)^{popcount(T\&k)}c_k\)
于是对做IFWT就能得到\(c\)
然后总复杂度就是\(O(nk2^k+(m+k)2^{m+k})\)
Code
#include<bits/stdc++.h>
using namespace std;
#define Fo(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define mo 998244353
#define N 1050010
#define M 20
namespace IO{
const int sz=1<<22;
char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
inline char gc(){
return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
}
template<class T>void read(T&x){
x=0;char c=gc();
for(;c<'0'||c>'9';c=gc());
for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
}
inline void flush(){fwrite(b,1,t-b,stdout),t=b;}
inline void pc(char x){*t++=x;if(t-b==sz)flush();}
template<class T>void write(T x,char c=' '){
if(x==0)pc('0');int t=0;
for(;x;x/=10)p[++t]=x%10+'0';
for(;t;--t)pc(p[t]);pc(c);
}
struct F{~F(){flush();}}f;
}
using IO::read;
using IO::write;
int n,m,k,a[M],p[N][M];
int mod(int x){return x>=mo?x-mo:x;}
int mi(int x,int y){
if(!y)return 1;
if(y==1)return x;
return y&1?1ll*x*mi(1ll*x*x%mo,y/2)%mo:mi(1ll*x*x%mo,y/2);
}
void FWT(vector<int>&A,int len,int x){
for(int mid=1;mid<len;mid<<=1){
for(int i=0;i<len;i+=(mid<<1)){
Fo(j,0,mid-1){
int t=A[i|j|mid];
A[i|j|mid]=mod(A[i|j]-t+mo);
A[i|j]=mod(A[i|j]+t);
}
}
}
if(x==-1){
int iv=mi(len,mo-2);
Fo(i,0,len-1)A[i]=1ll*A[i]*iv%mo;
}
}
int w[N];
vector<int>f[1<<10],g,h;
int main(){
read(n);read(m);k=3;
Fo(i,1,k)read(a[i]);
Fo(i,1,n) Fo(j,1,k)read(p[i][j]);
Fo(S,0,(1<<k)-1){
f[S].resize(1<<m);
Fo(i,1,n)w[i]=0;
Fo(i,1,k)if((1<<i-1)&S){Fo(j,1,n)w[j]^=p[j][i];}
Fo(i,1,n)f[S][w[i]]++;
FWT(f[S],1<<m,1);
}
g.resize(1<<k);
h.resize(1<<m);
Fo(S,0,(1<<m)-1){
Fo(i,0,(1<<k)-1)g[i]=f[i][S];
FWT(g,1<<k,-1);
h[S]=1;
Fo(i,0,(1<<k)-1){
int tmp=0;
Fo(p,1,k)tmp=mod(tmp+((1<<p-1)&i?mo-a[p]:a[p]));
h[S]=1ll*h[S]*mi(tmp,g[i])%mo;
}
}
FWT(h,1<<m,-1);
Fo(S,0,(1<<m)-1)write(h[S]);
return 0;
}