一个简单的组合意义做法

由 Kummer 定理（或 Lucas 定理），$a_i(t)$ 全部展开后为 $\oplus_{x\subseteq t}a_{(i-x+N)\bmod N}(0)$，其中 $x\subseteq t$ 表示二进制下 $x$ 所有 $1$ 的位置是 $t$ 所有 $1$ 的位置的子集。

设 $w_{h,t,k}$ 为 $2^h$ 盏灯的熄灭时刻恰好为 $t$，且初始有 $k$ 盏灯亮的方案数。对固定的 $h,t$，定义数列 $w_{h,t,k}$ 的普通生成函数为 $f_{h,t}(x)=\sum\limits_{k=0}^n w_{h,t,k}x^k$。

因为熄灭时刻恰好为 $t$ 有时候不太好处理，所以我们再定义一个熄灭时刻 $\le t$ 的生成函数，即 $g_{h,t}(x)=\sum\limits_{i=0}^tf_{h,i}(x)$，容易发现这等价于 $t$ 次操作后所有灯全部熄灭。

接下来我们尝试利用刚才的性质递推地解决问题。

当 $t$ 为偶数时，由于奇数位和偶数位是独立的，将其分离即可得到 $g_{h,t}=g_{h-1,t/2}^2$。

当 $t$ 为奇数时，可以理解为一次操作后变为 $t-1$ 时的情况，但这一次操作似乎导致 $1$ 的个数完全乱了，没法处理。

那该怎么办呢？我们再回到 $f$，容易发现熄灭时刻恰好为 $t$ 相当于 $t-1$ 次操作后所有灯都是亮的，即全为 $1$。

这样似乎又能递推了？将奇数位和偶数位分离，相当于它们在 $(t-1)/2$ 次操作后全变为 $1$，而这等价于熄灭时刻恰好为 $(t+1)/2$！那么我们得到了 $f_{h,t}=f_{h-1,(t+1)/2}^2$。

事实上，因为 $g_{h,t}=g_{h,t-1}+f_{h,t}$，所以其他情况可以直接用这个式子递推，容易发现每层只会访问 $O(1)$ 个不同的 $t$，因此时间复杂度为多项式乘法的 $O(n\log n)$。

代码相当好写：

map<array<int, 3>, poly> mp;
poly calc(int n, int k, int op)
{
    if (k == 0) return poly(n + 1) + poly{1};
    if (k == 1) return (op == 0 ? poly{1} << n : (poly{1} << n) + poly{1});
    if (k == n)
    {
        poly f(n + 1);
        if (op == 0) for (int i = 1; i <= n; i += 2) f[i] = C(n, i);
        else for (int i = 0; i <= n; i++) f[i] = C(n, i);
        return f;
    }
    if (mp.count({n, k, op})) return mp[{n, k, op}];
    if (op == 0)
    {
        if (k & 1)
        {
            poly f = calc(n >> 1, k + 1 >> 1, 0);
            return mp[{n, k, op}] = f * f;
        }
        else return mp[{n, k, op}] = calc(n, k, 1) - calc(n, k - 1, 1);
    }
    else
    {
        if (k & 1) return mp[{n, k, op}] = calc(n, k - 1, 1) + calc(n, k, 0);
        else
        {
            poly f = calc(n >> 1, k >> 1, 1);
            return mp[{n, k, op}] = f * f;
        }
    }
}

其实还可以注意到 $t$ 是偶数的时候 $f_{h,t}=2f_{h-1,t/2}g_{h-1,t/2-1}$，可以进一步减小常数。

QOJ.ac

QOJ

Discussion #3139 for Problem #21429. Tomoshibi

Comments