我的做法是 $O(3^d)$ 的，这个我计算过了

官方题解也是 $O(3^d)$ 的，但是为啥我就 TLE？？？

code

int main()
{
	int n=rd();
	int mx=0,mxb=1;
	while(n--) {int a=rd();mx=max(mx,a);++cnt[a];}
	while(mxb<=mx) mxb<<=1;
	--mxb;
	shai();
	ans[0]=1;F(i,1,cnt[0]) {ans[0]*=2;(ans[0]>=p)&&(ans[0]-=p);}
	cnt[0]=0;
	F(s,1,mx) {re int x=mxb^s;for(ri i=x;;i=(i-1)&x) {ans[i^s]=(ans[i^s]+1ll*ans[i]*cnt[s])%p;if(!i)break;}}
	int res=0;
	F(s,0,mxb) res=(res+1ll*ans[s]*phi[s+1])%p;
	printf("%d\n",res);
	return 0;
}

我寻思 3.5e8(352187208) 次 1ll*int*int%int T 不了吧……