首先先考虑刻画原问题，熟知 $\bmod x^N-1$ 即为将指数 $\bmod N$，因此即为对底域在 $F_2$ 上 $\deg f(x)< N \land f(1)=i$ 且 $T$ 是最小的自然数使得 $(1+x)^T f(x)\bmod (x^N-1)=0$。

我们熟知当 $\log_2 N\in\mathbb{N}$ 时在 $2$ 特征域上有 $(1+x)^N=1+X^N=X^N-1$，因此即为求 $$ \sum_{f(x)\in F_2[x]}\left[\deg f(x) < N \land (1+x)^{N-T}\parallel f(x)\right]t^{f(1)} $$

这个恰好整除有点麻烦，我们不妨平移到以 $(x+1)$ 为基底，由 Lucas 定理可知在 $2$ 特征域上平移 $1$ 即为做二进制高维前缀和（记为 $\zeta$），也就是我们要求限制 $\forall i\leq N-T, g_i=[i=N-T]$，然后计数 $\sum_i (\zeta\cdot g)_i=k$ 的 $g$ 个数。

考虑在字典树上定位 $N-T$。

往左走时，右子树可以随便填，由于 $\zeta$ 可逆（特征为 $2$ 时逆变换就是它本身），因此右子树的 $\zeta g$ 是均匀分布的，因此你对于左子树只需要记录局部的 $\zeta$ 变换后每一种 $1$ 个数对应的方案数即可，对于同样 $1$ 个数的方案，考虑到右子树影响后由于右子树分布均匀所以每一位都对称，对最终 $1$ 个数分布的影响是一致的，因此就在多项式时间内归约到了子问题。

先考虑往右走：左子树全填 $0$，因此左子树的 $\zeta$ 此时与右子树一致，刚才说了我们只关心子树内 $1$ 个数分布，于是直接把原先记录的 $1$ 个数翻倍即可。

往右走显然是 $\Theta(N)$ 的，假如往左走的复杂度是 $F(N)=\Omega(N)$ 的话时间复杂度即为 $T(N)=T(\frac{N}{2})+F(N)=F(N)$ 的。

我们现在显然会 $F(N)=O(N^3)$，因为你的转移是 $f_i$ 枚举 $j,k$ 以 $\binom{i}{k}\binom{N-i}{j-k}$ 的系数贡献到 $i+j-2k+j$ 上。

写出来这个矩阵系数 $A_(i,j)=\sum_k \binom{i}{k}\binom{N-i}{\frac{j-i}{2}}=2^i\binom{N-i}{\frac{j-i}{2}}$

显然 $A_{i,j}\neq 0$ 的 $i,j$ 同奇偶，先枚举奇偶 $o$，于是即为 $A_{2i+o,2j+o}=2^{2i+o}\binom{N-2i-o}{j-i}=2^{2i+o} [t^j] x^i (1+t)^{N-2i-o}$

于是你记 $F_o(t)=\sum_i 2^{2i+o}f_{2i+o} t^i$，所求即为 $(1+t)^{N-o}F_o(\frac{t}{(1+t)^2})$。

熟知当内层为二次比二次分式可以 $O(N\log N)$ 完成复合，但是考虑到可能确实不是所有人都会，还是具体记述一下此处做法：

具体来说，我们可以翻转一下变为计算 $\circ \frac{(1+t)^2}{t}$，可以先平移掉常数项再放缩变为 $\circ \frac{t+t^{-1}}{2}$，然后有 $\frac{t+t^{-1}}{2}=\frac{t+1}{t-1}\circ t^2\circ \frac{t+1}{t-1}$，这个构造是考虑到 $\frac{t+t^{-1}}{2}$ 关于 $t,t^{-1}$ 对称，于是我们猜测复合链形如 $g(t)\circ t^2\circ h(t)$，其中 $g,h$ 都是一次比一次分式，然后要求 $g(t)+g(t^{-1})=0$，解一下可以解出来 $g$，再解一下 $h(g^2(t))=t+t^{-1}$ 即可，然后很神奇的发现 $g(t)=h(t)=\frac{t+1}{t-1}$。

再考虑下怎么做 $\circ \frac{t+1}{t-1}$，这个是 $\frac{t+1}{t-1}=(t+1)\circ 2t \circ \frac{1}{t-1}$，$\circ \frac{1}{t-1}$ 可以类似平移那样构造卷积。

于是我们就得到了一个 $\Theta(N\log N)$ 做法。