[cf1336E]Chiori and Doll Picking

将所有$a_{i}$在二进制下展开，得到一个$n\times m$的01矩阵

对该矩阵做高斯消元（显然不影响结果），并要求得到如下的形式
$$
\left|\begin{array}{ll}
1&0&0&\cdots&0&\cdots\\
0&1&0&\cdots&0&\cdots\\
0&0&1&\cdots&0&\cdots\\
\vdots&\vdots&\vdots&\ddots&\vdots&\ddots\\
0&0&0&\cdots&1&\cdots
\end{array}\right|
$$
形式：假设其有$k$行，左边$k$列中仅主对角线为1（其余均为0），右边$m-k$列任意

另外，其余的$n-k$个$a_{i}$均为0，进而贡献即将答案乘上$2^{n-k}$（以下不再考虑）

在此基础上，暴力枚举$a_{i}$是否选择并$o(1)$计算$cnt(x)$（$x$在二进制下1的个数），时间复杂度为$o(2^{k})$

令$f_{i,j,x}$表示$a_{[1,i]}$中选$j$个且右侧结果为$x$的方案数（左边1的个数即为$j$），时间复杂度为$o(k^{2}2^{m-k})$

结合上述两个做法，对$k\le \frac{m}{2}+\log m$分类讨论，总复杂度为$o(m2^{\frac{m}{2}})$

对于$m\le 53$的hard version，考虑优化上述做法后半部分的复杂度：

记$A_{x}$为结果为$x$的方案数，注意到任意两种选法左侧均不同，即$A_{x}\in \{0,1\}$

构造$G^{c}_{x}=[cnt(x)=c]$，那么$ans_{c}=(A\bigoplus G^{c})_{0}$即为答案（其中$\bigoplus$为异或卷积）

使用FWT计算$\bigoplus$，结合其式子，不难得到（答案为）
$$
ans_{c}=\frac{\sum_{x=0}^{2^{m}-1}{\rm FWT}(A)_{x}\cdot{\rm FWT}(G^{c})_{x}}{2^{m}}
$$

性质1：$\forall 0\le x<2^{m},{\rm FWT}(A)_{x}\in \{0,2^{k}\}$

根据$A$的意义，不难得到$A_{x}=1\Longrightarrow \forall 0\le i<2^{m},A_{i}=A_{x\oplus i}$

考虑$A\bigoplus A$，代入可得$(A\bigoplus A)_{x}=\sum_{A_{i}=1}A_{x\oplus i}=\sum_{A_{i}=1}A_{x}=2^{k}A_{x}$

使用FWT计算$\bigoplus$，即$\big({\rm FWT}(A)_{x}\big)^{2}=2^{k}{\rm FWT}(A)_{x}$，解得${\rm FWT}(A)_{x}\in \{0,2^{k}\}$，即得证

另一方面，注意到${\rm FWT}(G^{c})_{x}$仅由$cnt(x)$确定，即
$$
{\rm FWT}(G^{c})_{x}=\sum_{i=0}^{c}(-1)^{i}{cnt(x)\choose i}{m-cnt(x)\choose c-i}
$$
枚举$cnt(x)$，结合性质1，仅需统计其中${\rm FWT}(A)_{x}=2^{k}$的$x$个数

记该值为$F_{cnt(x)}$，注意到其与$c$无关，同时求出$F$后代入之前的式子即可$o(m^{3})$求出$ans$

性质2：${\rm FWT}(A)_{x}=2^{k}$当且仅当$\forall 1\le j\le k,2\mid cnt(x\&a_{j})$

代入FWT的式子，即${\rm FWT}(A)_{x}=\sum_{A_{i}=1}(-1)^{cnt(x\&i)}\le 2^{k}$

同时，等号取到的条件为$\forall A_{i}=1,2\mid cnt(x\&i)$，显然$A_{a_{j}}=1$即得到必要性

关于充分性，注意到$cnt(i\&(x\oplus y))\equiv cnt(i\&x)+cnt(i\&y)(mod\ 2)$

对于$A_{i}=1$，存在集合$S$使得$\bigoplus_{j\in S}a_{j}=i$，进而$cnt(x\&i)\equiv \sum_{j\in S}(x\&a_{j})\equiv 0(mod\ 2)$

综上，即得证

枚举$x$的后$m-k$位$x'$，结合性质2，有$cnt(x)=cnt(x')+\sum_{j=1}^{k}[2\not\mid cnt(x'\&a_{j})]$

暴力枚举$x'$，并在过程中维护$\forall 1\le j\le k,[2\not\mid cnt(x'\&a_{j})]$，最终统计到$F_{cnt(x)}$即可

后半部分的复杂度被降为$o(2^{m-k}+m^{3})$，对$k\le \frac{m}{2}$分类讨论，总复杂度为$o(2^{\frac{m}{2}}+m^{3})$

结合初始的高斯消元，最终总复杂度为$o(nm+2^{\frac{m}{2}}+m^{3})$，可以通过

 1 #include
 2 using namespace std;
 3 #define N 200005
 4 #define M 60
 5 #define mod 998244353
 6 #define ll long long
 7 #define count __builtin_popcountll
 8 int n,m,k,P[M];
 9 ll a[N];
10 ll change(ll x){
11     ll ans=0;
12     for(int i=0;i)
13         if ((x>>P[i])&1)ans|=(1LL<<i);
14     return ans;
15 }
16 namespace Subtask1{
17     int ans[M];
18     void dfs(int i,ll s){
19         if (i==k){
20             ans[count(s)]++;
21             return;
22         }
23         dfs(i+1,s),dfs(i+1,(s^a[i]));
24     }
25     void main(){
26         dfs(0,0);
27         int s=1;
28         for(int i=0;i1)%mod;
29         for(int i=0;i<=m;i++)ans[i]=(ll)ans[i]*s%mod;
30         for(int i=0;i<=m;i++)printf("%d ",ans[i]);
31     }
32 };
33 namespace Subtask2{
34     int C[M][M],F[M],ans[M];
35     ll b[M];
36     void dfs(int i,ll s){
37         if (i==m){
38             F[count(s)]++;
39             return;
40         }
41         dfs(i+1,s),dfs(i+1,(s^b[i]));
42     }
43     void main(){
44         for(int i=k;i){
45             b[i]=(1LL<<i);
46             for(int j=0;j)
47                 if ((a[j]>>i)&1)b[i]|=(1LL<<j);
48         }
49         dfs(k,0);
50         for(int i=0;i<=m;i++){
51             C[i][0]=C[i][i]=1;
52             for(int j=1;j1][j-1]+C[i-1][j])%mod; 
53         }
54         for(int i=0;i<=m;i++)
55             for(int j=0;j<=m;j++){
56                 int s=0;
57                 for(int k=0;k<=i;k++){
58                     int ss=(ll)C[j][k]*C[m-j][i-k]%mod;
59                     if (k&1)ss=mod-ss;
60                     s=(s+ss)%mod;
61                 }
62                 ans[i]=(ans[i]+(ll)s*F[j])%mod;
63             }
64         int s=1;
65         for(int i=0;i1)%mod;
66         for(int i=0;i1>>1)%mod;
67         for(int i=0;i<=m;i++)ans[i]=(ll)ans[i]*s%mod;
68         for(int i=0;i<=m;i++)printf("%d ",ans[i]);
69     }
70 };
71 int main(){
72     scanf("%d%d",&n,&m);
73     for(int i=0;i"%lld",&a[i]);
74     for(int i=0;ii;
75     for(int i=0;i){
76         int pos=-1;
77         for(int j=k;j)
78             if ((a[j]>>i)&1){
79                 pos=j;
80                 break;
81             }
82         if (pos<0)continue;
83         swap(P[k],P[i]),swap(a[k],a[pos]);
84         for(int j=0;j)
85             if ((j!=k)&&((a[j]>>i)&1))a[j]^=a[k];
86         k++; 
87     }
88     for(int i=0;ichange(a[i]);
89     if (k<=(m>>1))Subtask1::main();
90     else Subtask2::main();
91     return 0;
92 }