loj6737

前言

喜提最劣解。

此做法系与神 SegmentTree 交流得到。

在此前，你能在网上找到的题解似乎只有某神仙的神秘做法，反正我根本不会。

故，本篇题解要旨在于给出思维的过程。

Version 1

读题。

你有一个正整数集合 /(S/)，现在请你回答对于 /(1/le k/le n/)，有多少种将编号为 /(1/sim k/) 的球放入一些盒子的方案，使得每个盒子里球的数量都属于 /(S/)。你只想知道答案的奇偶性（对 /(2/) 取模）。

注意：球可以区分，盒子不可以区分。

/(n/le 10^6/)，时限 /(1s/)。

如果模 /(998244353/)，这不就是个带标号 /(/operatorname{SET}/) 的事！直接 EGF 上 /(/exp/) 不就好了！

模 /(2/) 就很难受了。

由 Lucas 定理，二项卷积就是不交并卷积（子集卷积），因为在模 /(2/) 意义下：

/[/binom ST=[T/subset S]
/]

故 EGF 与集合幂级数对其计数序列的乘法操作在模 /(2/) 时是一致的。

容易验证的是，加减法也保持一致。

那么我们是不是用集合幂级数 /(/exp/) 就做完了？

不是。

/[/exp F=/sum_n{F^n/over n!}
/]

即，我们漏考虑了：/(/exp/) 在定义时要求了数乘运算，而我们忽略了它内部的 /(n!/) 在 /(/mod 2/) 意义下并不必然可逆。

换句话说，我们的做法寄了。

Version 2

我们考虑如何规避掉数乘。

也就是说，我们可以先通过 EGF 推柿子把数乘扔掉，然后再来用集合幂级数计算答案。

咋推？

注意到

/[/exp/sum A=/prod/exp A
/]

我们只用推导 /(/exp{z^n/over n!}/) 的计数序列奇偶性就好了。

Version 3

/[/texttt{Lemma}/ 1:/exp{z^n/over n!}=/sum_{k/ge0}{z^{nk}/over(nk)!}/prod_{t=1}^k/binom{nt-1}{n-1}
/]

考虑组合意义，即把 /(nk/) 个数分成 /(k/) 个大小为 /(n/) 的无序组。

通过枚举第一个数和哪些数分入一组即得此式。

/[/texttt{Lemma}/ 2:2/nmid/binom{2n-1}{n-1}/Leftrightarrow/log_2n/in/mathbb N
/]

由 Lucas 定理可证。

/[/texttt{Lemma}/ 3:2/nmid[{z^m/over m!}]/exp{z^n/over n!}/Leftrightarrow(/log_2n/in/mathbb N/land n|m)/lor(/log_2n/notin/mathbb N/land(m=0/lor m=n))
/]

说人话，/(n/) 为 /(2/) 的幂次时其在 /(0,n,2n,3n,/dots/) 处计数序列为奇数；否则，仅在 /(0,n/) 处为奇数。

这个由前两个 /(/texttt{Lemma}/) 立刻可得。

Version 4

考虑应用上述 /(/texttt{Lemma}/ 3/)。

/[/exp/sum_{k/in S}{z^k/over k!}=/prod_{k/in S}/exp{z^k/over k!}
/]

把 /(/log_2k/in/mathbb N/) 的 /(k/) 单独计算，构成集合 /(T/)；其余的也单独计算，构成集合 /(S-T/)，每个元素表示集合幂级数的”集合”时记为集族 /(/mathcal U/)。

对于 /(k/in T/)，我们发现每次乘法相当于在对应维度做了子集求和，直接做就好了。

对于 /(k/in S-T/)，我们有 /(/prod_{A/in/mathcal U}(z^/varnothing+z^A)=/prod_{0/le p/le/log_2N}(z^/varnothing+/sum_{A/text{ 的最大元素为 }p}z^A)/)，从小到大乘即可。

最后再用一次集合幂级数乘法合并两部分答案。

Code

我们如果利用压位来实现集合幂级数乘法，复杂度是 /(O({n/log^2n/over w})/) 的，总复杂度也是这个级别。

但是这个做法不知道为啥常数特别大，卡常卡常卡常开 Ofast 开 32 位配置千辛万苦才跑了过去。

代码比较短，不足 /(2kb/)。

// Problem: #6737. 指数公式
// Contest: LibreOJ
// URL: https://loj.ac/p/6737
// Memory Limit: 256 MB
// Time Limit: 1000 ms

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
voi FMT(uint*A,uint n){for(uint i=1;i<n;i<<=1)for(uint j=0;j<i;j++)for(uint k=0;k<n;k+=i<<1)A[i|j|k]^=A[j|k];}
const uint Lim=1u<<21;
chr C[Lim|1];uint Now[Lim|1],A[Lim|1],B[Lim|1];
#define popcnt(v) __builtin_popcount(v)
int main()
{
    scanf("%s",C+1);uint N=0;while(C[N+1])N++;
    Now[0]=A[0]=A[1]=1;
    for(uint i=Lim>>1;i;i>>=1)
    {
    	for(uint j=Lim/i-1;~j;j--)Now[j]=(j&1)?0:Now[j>>1];
    	if(C[i]=='1')FMT(Now,Lim/i);
    }
    for(uint i=0;i<Lim;i++)if(Now[i])Now[i]=1u<<popcnt(i);
    for(uint w=4,q=2;w<=Lim;w<<=1,q++){
    	for(uint i=0;i<(w>>1);i++)A[i|(w>>1)]=A[i];
    	B[0]=1;for(uint i=w>>1|1;i<w;i++)if(C[i]=='1')B[i]=1u<<popcnt(i);
    	FMT(B,w);
    	for(uint i=0;i<w;i++){
    		uint t=0;while(B[i])t^=A[i]*lowbit(B[i]),B[i]^=lowbit(B[i]);
    		A[i]=t;
    	}
    }
    FMT(Now,Lim);
    for(uint i=0;i<Lim;i++)
	{
		uint t=0;while(Now[i])t^=A[i]*lowbit(Now[i]),Now[i]^=lowbit(Now[i]);
		A[i]=t;
	}
	FMT(A,Lim);
	for(uint i=1;i<=N;i++)putchar((A[i]>>popcnt(i)&1)+'0');
    return 0;
}