咋一看，至少要用3^n才能做到。

但。

首先定义：

可以发现只要求出a' b' 那么直接可以得出c'

那么如何求a'呢

//dp求a',其实就是分别用[0,n)来更新a'for (int i = 0; i < n; i++)    for (int s = 0; s < (1 << n); s++)        if (s >> i & 1)            a[s] += a[s ^ 1 << i];

有了a'之后，观察式子发现直接逆着写，就可以从a'->a

然后反演即为：

for (int i = 0; i < n; i++)    for (int s = 0; s < (1 << n); s++)        if (s >> i & 1)            c[s] -= c[s ^ 1 << i];

然后就可以在n*2^n 内求出C

参考: