有如下的一个FWT函数：

for(int i=0;i<n;i++){
	for(int j=0;j<state;j++)
    	if(j&(1<<i)) ad(a[j],a[j^(1<<i)),ad(b[j],b[j^(1<<i)]);
	for(int j=state-1;~j;j--)
    	if(!(j&(1<<i))) ad(c[j],c[j^(1<<i)),ad(d[j],d[j^(1<<i)]);
}

在这种FWT下，整个代码运行速度是 $17s$。

但内层循环我只要注释掉任意一个，运行速度就骤降至 $2s$。

场上因为这个东西思索了1h。

请问这是什么原因呢。

函数其他部分的复杂度都是确定的，不会因为 FWT 出来的值改变而改变。