Preface

妈的期中考终于结束了，感觉在区域赛前抽出将近两周的时间不训练去复习有点得不偿失的说

现在终于有时间来补一下题，其实手头要补的题还挺多的，一个是上次CCPC桂林打完后可做的一些题，另一个是这段时间零碎地练习的两场

一场台湾的网络赛有两个题赛时卡着都没写出来，过两天补一下；另一个就是这周一队友两个人VP了场ICPC沈阳，因为我晚上有大物实验所以没怎么打，只中间抽空去了90min口胡了几个简单题，这场也有一些题要补

再剩下的就是这段时间拉下的CF，ATC之类的了，而且合肥站之后还有大概率要去的川渝省赛，又要开始忙起来了

Solution

回到这题，这题其实一点不难，所有trick的转化在比赛的时候祁神都看出来了，但就是因为不知道线性基能计数然后做不出来，顺带导致我后面两小时一点作用没有

这题的破局关键就在于要发现\(\bigoplus_{j=1}^m a_{i_j}<2\times \max_{j=1}^m(a_{i_j})\)，因此要满足倍数关系，则必须有\(\bigoplus_{j=1}^m a_{i_j}=\max_{j=1}^m(a_{i_j})\)，同时选取的所有数必须都是\(\max_{j=1}^m(a_{i_j})\)的约数

我们可以大力枚举\(\max_{j=1}^m(a_{i_j})\)的值\(x\)，并求出\(x\)真因子构成的集合\(S\)，很显然\(S\)中所有数异或起来一定小于\(x\)，因此要让\(\bigoplus_{j=1}^m a_{i_j}=x\)，则必须至少选取一个\(x\)

那么直接枚举选择了多少个\(x\)（一定是奇数个），然后此时相当于要求在集合\(S\)中任选一些数使得它们的异或和为\(0\)的方案数

根据线性基原理，设线性基中自由变量的个数为\(free\)，则方案数为\(2^{free}\)，在插入的时候顺带统计下即可

最后还有一种特殊情况就是\(\bigoplus_{j=1}^m a_{i_j}=0\)，直接用线性基统计所有数构成的集合选出数来异或为\(0\)的方案即可

总复杂度\(O(n\log^2 n)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005,mod=998244353;
int t,n,x,c[N],fact[N],ifac[N],pw[N]; vector <int> frac[N];
struct LB //Linear_Basis
{
	int p[20],free;
	inline void clear(void)
	{
		memset(p,0,sizeof(p)); free=0;
	}
	inline void insert(int x)
	{
		for (RI i=19;i>=0;--i) if ((x>>i)&1)
		{
			if (!p[i]) return (void)(p[i]=x); x^=p[i];
		}
		++free;
	}
}A,B;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i,j; for (i=1;i<=n;++i) for (j=2*i;j<=n;j+=i) frac[j].push_back(i);
	for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
	for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
}
inline int C(CI n,CI m)
{
	return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t),init(200000);t;--t)
	{
		RI i,j; A.clear(); for (scanf("%d",&n),i=1;i<=n;++i)
		scanf("%d",&x),A.insert(x),++c[x]; int ans=pw[A.free];
		for (i=1;i<=n;++i) if (c[i])
		{
			B.clear(); int ret=0; for (j=1;j<=c[i];j+=2) (ret+=C(c[i],j))%=mod;
			for (auto x:frac[i]) if (c[x]) B.insert(x),B.free+=c[x]-1;
			(ans+=1LL*ret*pw[B.free]%mod)%=mod;
		}
		for (printf("%d\n",(ans-1+mod)%mod),i=1;i<=n;++i) c[i]=0;
	}
	return 0;
}