我怎么感觉只有一篇题解(那篇涉及EGF的)我能理解呢?其他都是逆向题解吗


还是首先先推式子,设 $f_{i,j}$ 表示前 $i$ 个数,有 $j$ 个 $1$ (无关于具体位置)的方案数。

由于无关于具体位置,那么答案为 $\sum\limits_{i=n}^{k}f_{n,i}*\dbinom{k}{i}$

考虑递推:

$$f_{i,j}=\sum\limits_{l=1}^{j-1}f_{i-1,l}\dbinom{j}{l}2^{l}$$

意义为:选择一个 $a_i$ ,使得 $b_i$ 有 $j$ 个 $1$ ,$a_1|a_2|\ldots|a_{i-1}$ 已经包含了 $l$ 个,那么 $a_i$ 必须包含除这 $l$ 个

之外的位置的 $1$ ,相当于有 $j$ 个数,让你从中选出 $j-l$ 个数, 就可以得到方案数 $\dbinom{j}{l}$ 。然后 $a_i$ 还可以选择性的含有 $l$ 中 $1$ ,即 $2^l$ 。

显然这个式子可以卷积,也很容易得到 $EGF$。

$F_{n-1}(x)=\sum\limits_{i}f_{n-1,i}\frac{x^i}{i!},e^x-1=\sum\limits_{i}\frac{x^i}{i!}$

观察上述转移方程,实际上 $F_{n}(x)=\sum_{i}(\sum_{j}2^j\dbinom{i}{j}f_{n-1,j})\frac{x^i}{i!}=(e^x-1)F_{n-1}(2x)$

($F(cx)=\sum_ic^i\frac{x^i}{i!}$)

$F_{n-1}(2x)=(e^{2x}-1)F_{n-2}(4x)$

如此往复下去,就可以得到这样一个优美的式子,

$F_{n}=\prod\limits_{i=0}^{n-1}(e^{2^ix}-1)$

边界: $F_0=0,F_{1}=e^x-1$

之后就是套路倍增,关于这一步,大部分题解里面的解释都是口胡或者是感性的理解,所以我们来推一下吧!

$\begin{aligned}F_{2n}&=\prod\limits_{i=0}^{2n-1}(e^{2^ix}-1)\\&=\prod\limits_{i=0}^{n-1}(e^{2^ix}-1)\prod\limits_{i=0}^{n-1}(e^{2^{n+i}x}-1)\\&=\prod\limits_{i=0}^{n-1}(e^{2^ix}-1)\prod\limits_{i=0}^{n-1}(e^{2^i2^nx}-1)\end{aligned}$

观察后式,完全可以换元 $u=2^nx$

$\begin{aligned}F_{2n}&=F_n(x)F_n(u)\\&=F_n(x)F_{n}(2^nx)\end{aligned}$

展开回原式:

其中 $F_n(2^nx)$ 展开是这样的:

$\large\sum\limits_{i}2^{in}\frac{x^i}{i!}$

于是卷积之后为:

$\large f_{2n,i}\frac{x^{i}}{i!}=(\sum\limits_j\dbinom{i}{j}2^{jn}f_{n,j}f_{n,i-j})\frac{x^{i}}{i!}$

同样地,也可以卷积,记得用MTT。

优化细节自己想吧,不想卡常了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n)) 
using namespace std;
const int N=4e5+5,mod=1e9+7,M=1<<15;
const double pi=acos(-1);
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
I int ksm(int a,int b=mod-2){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
struct cp
{
    double x,y;
    cp(double x=0.0,double y=0.0):x(x),y(y){}
    I cp operator +(const cp &a)const{return cp(x+a.x,y+a.y);}
    I cp operator -(const cp &a)const{return cp(x-a.x,y-a.y);}
    I cp operator *(const cp &a)const{return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
    I cp operator /(const double &a)const{return cp(x/a,y/a);}
    I cp operator *(const double &a)const{return cp(x*a,y*a);}
    I cp operator +(const double &a)const{return cp(x+a,y+a);}
}w[N<<1];
cp Ii=cp(0,1);
int tr[N<<1],cnt;
I void rev(int n)
{
    if(cnt==n)return ;cnt=n;
    for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1|((i&1)?n>>1:0));
}
I void Init(int n){for(int i=1;i<n;i<<=1){w[i]=cp(1,0);for(int j=1;j<i;j++)w[i+j]=(((j&31)==1)?cp(cos(pi*j/i),sin(pi*j/i)):w[i+j-1]*w[i+1]);}}
void dft(cp *g,bool op,int n)
{
    rev(n);
    static cp f[N<<1],t;
    for(int i=0;i<n;i++)f[i]=g[tr[i]];
    for(int p=2,l=1;p<=n;l=p,p<<=1)
        for(int i=0;i<n;i+=p)for(int j=0;j<l;j++)
            t=w[j|l]*f[i|j|l],f[i|j|l]=f[i|j]-t,f[i|j]=f[i|j]+t;
    if(op)for(int i=0;i<n;i++)g[i]=f[i]/n;
    else for(int i=0;i<n;i++)g[i]=f[i];
}
cp a0[N<<1],a1[N<<1],b0[N<<1],b1[N<<1],p[N<<1],q[N<<1];
void calc(cp *a,cp *b,int n)
{
    for(int i=0;i<n;i++)p[i]=a[i]+Ii*b[i];
    dft(p,0,n);q[0]=cp(p[0].x,-p[0].y);
    for(int i=1,j=n-1;i<n;i++,j--)q[i]=cp(p[j].x,-p[j].y);
    for(int i=0;i<n;i++)a[i]=(p[i]+q[i])*0.5,b[i]=(q[i]-p[i])*0.5*Ii;
}
ll num(double x){return x<0?(ll)(x-0.49)%mod:(ll)(x+0.49)%mod;}
void mtt(int *f,int *g,int m)
{
    int n=1;for(;n<(m<<1);n<<=1);
    for(int i=0;i<m;i++)a0[i]=cp(f[i]>>15,0),a1[i]=cp(f[i]&(M-1),0);
    for(int i=0;i<m;i++)b0[i]=cp(g[i]>>15,0),b1[i]=cp(g[i]&(M-1),0);
    for(int i=m;i<n;i++)a0[i]=a1[i]=b0[i]=b1[i]=cp(0,0);
    
    calc(a0,a1,n);calc(b0,b1,n);
    for(int i=0;i<n;i++)p[i]=a0[i]*b0[i]+Ii*a1[i]*b0[i],q[i]=a0[i]*b1[i]+Ii*a1[i]*b1[i];
    reverse(p+1,p+n),reverse(q+1,q+n);
    dft(p,1,n),dft(q,1,n);
    for(int i=0;i<m;i++)f[i]=(1ll*M*M%mod*num(p[i].x)%mod+1ll*M*num(p[i].y+q[i].x)%mod+num(q[i].y)+4ll*mod)%mod;
    for(int i=m;i<n;i++)f[i]=0;
}
int f[N],sav[N],g[N];//f[i]->f[i]/i!
int fac[N],ifac[N],k,dfac[N],pw[N];
void init(int m)
{    
    fac[0]=ifac[0]=pw[0]=1;for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%mod,pw[i]=pw[i-1]*2%mod;
    dfac[0]=1;for(int i=1;i<=m;i++)dfac[i]=1ll*dfac[i-1]*(k-i+1)%mod;
    ifac[m]=ksm(fac[m]);for(int i=m-1;i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
void add(int m)
{
    for(int i=1;i<m;i++)f[i]=1ll*f[i]*pw[i]%mod*ifac[i]%mod;
    mtt(f,sav,m);
    for(int i=1;i<m;i++)f[i]=1ll*f[i]*fac[i]%mod;
}
void mul(int l,int m)
{
    for(int i=1;i<m;i++)f[i]=1ll*f[i]*ifac[i]%mod;cpy(g,f,m);
    for(int i=1;i<m;i++)f[i]=1ll*f[i]*ksm(pw[l],i)%mod;
    mtt(f,g,m);
    for(int i=1;i<m;i++)f[i]=1ll*f[i]*fac[i]%mod;
}
int C(int n,int m)
{
    if(n<m)return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
ll n;
int main()
{
    qr(n),qr(k);int t=n;
    if(n>k){puts("0");return 0;}
    init(k);
    int m=k+1;
    for(n=1;n<(m<<1);n<<=1);
    Init(n);for(int i=1;i<m;i++)f[i]=1,sav[i]=ifac[i];
    int lg=log2(t),j=1;
    for(int i=lg-1;~i;i--)
    {
        mul(j,m);j<<=1;
        if(t&(1<<i))
            add(m),j|=1;
    }
    ll ans=0;
    for(int i=1;i<=k;i++)
        ans=(ans+1ll*f[i]*C(k,i)%mod)%mod;
    qw(ans);puts("");
    return 0;
}