卷积

convolution
也叫折积

多项式乘法

for (int i = 0; i <= n; i++)
{
	for (int j = 0; j <= n; j++)
	{
		c[i + j] += a[i] * b[j];
	}
}

异或卷积

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		c[i ^ j] += a[i] * b[j];
	}
}

或卷积

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		c[i | j] += a[i] * b[j];
	}
}

与卷积

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		c[i & j] += a[i] * b[j];
	}
}

先离散对数再卷积

for (int i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		c[(i * j) % n] += a[i] * b[j];
	}
}

狄利克雷卷积

for (int i = 1; i <= n; i++)
{
	for (int j = 1; i * j <= n; j++)
	{
		c[i * j] += a[i] * b[j];
	}
}