不得不说是一道多项式神题了。
虽然说颓代码颓的很厉害不过最终A掉了。
好好讲一讲这道题。
涉及的知识点是：高阶导数，NTT，指数型母函数，泰勒公式，以及意志力和数学推导能力。
那就开始了。
一个测试点一个测试点来。
首先注意到$b[i]=lim_{i=1}^{i<=n}(|=a[i])$
1.$n,k<=4$ 直接爆搜。$O(2^{nk})$
2.$n,k<=10$考虑状压dp。
设$dp[i][s]$为$a$的$i$项前缀或和。
那么有转移$dp[i+1][s|t]+=dp[i][s]*[(s|t)!=s]$
这样是$O(n4^{k})$
3.$n,k<=300$。
首先优化状压dp，我们其实并不关心状压dp中状态的1是那些1，我们只关心有几个1。
那么得到$dp[i][j]$前$i$位的$a$或和中有$j$个1，且清楚是哪些1的方案数。
$dp[i][j]=\sum\limits_{k=0}^{j-1}dp[i-1][k]2^kC_{K-k}^{j-k}$
复杂度是$O(nk^2)$
4.59分
优化上述$dp$
其实可以看到卷积的影子吧。
设$g[i][j]$前$i$位的$a$或和中有$j$个1，不清楚是那些1的方案数。
$g[i][j]=\sum\limits_{k=0}^{j-1}g[i-1][k]2^kC_j^{j-k}$
那么$dp[i][j]=C_K^jg[i][j]$
可以看出来g是一个卷积的形式了。
那么复杂度$O(nklogk)$
5.AC
优化上述dp。
改变g的枚举方式。
$g[i][j]=\sum\limits_{k=1}^{j}g[i-1][j-k]2^{j-k}C_{j}^{k}$
展开组合数。
$g[i][j]=\sum\limits_{k=1}^{j}g[i-1][j-k]2^{j-k}\frac{j!}{k!(j-k)!}$
那么也就是说
$\frac{g[i][j]}{j!}=\frac{\sum\limits_{k=1}^{j-1}g[i-1][j-k]2^{j-k}}{j!}\frac{1}{k!(j-k)!}$
可以看出指数型母函数的样子了。
生成函数$G(x)=\sum\limits_{k=1}^{j-1}\frac{g[i][j]}{j!}$
引入泰勒公式。
$++$为正无穷。
对于任何一个函数$f$
$f(x)=\sum\limits_{i=0}{++}\frac{f^{(i)}(x_0)(x-x_0)^i}{i!}$
证明：
首先$f(x)=f(x_0)+f^{(1)}(x_0)(x-x_0)=f(x_0)(x-x_0)^0+f^{(1)}(x-x_0)^1,x->x_0$
往下接着写就是
$f(x)=\sum\limits_{i=0}^{++}f{(i)}(x_0)(x-x_0)^i$
对$f(x_0)^{(m)}(x-x_0)^m$求$m$阶导。
首先$x^n$的导数为$nx^{n-1}$
那么
1.$mf(x_0)^{m-1}(x-x_0)^{m-1}$
2.$m(m-1)f(x_0)^{m-2}(x-x_0)^{m-2}$
......
m.$m!f(x_0)$
在往后都是0了，$m!f(x_0)$是常数。
那么其实$f^{(m)}(x_0)=m!f(x_0)$因为其他项带$(x-x_0)$，所以都是0。
除掉$m!$
得到泰勒公式的结论了。
原文：https://www.cnblogs.com/Lrefrain/p/11587631.html