B. 酒杯

标签：conv tar int res maxn 酒杯 define

题意

给定 \(n\) 和 \(m\)，问将 \(m\) 个点随机放在一个深度为 \(n\) 的满二叉树的节点上后，每一层至少有一个点的方案数。

---

思路

首先，我们发现正着直接算会有一个很麻烦的地方就是若多个点放在同一个点上，那么方案数就要除上 \(siz!\)。

于是我们考虑反着算，即容斥。我们可以钦定哪几层的节点是不能选的，然后乘上一个容斥系数即为答案。具体来说：

\[\]

---

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define file(x,y) freopen(x,"r",stdin),freopen(y,"w",stdout);
#define tup tuple<int,int,int,int>
#define pii pair<int,int>
#define pb emplace_back
#define i12 __int128_t
#define mt make_tuple
#define mp make_pair

const int      maxn=2e3+10;
const int      mod=1e9+7;

int c[maxn][maxn],f[maxn][maxn];
int n,m,res[maxn];

int power(int a,int b,int p){int tar=1;for(; b; (a*=a)%=p,b>>=1)if(b&1)(tar*=a)%=p;return tar;}

void conv(int *f,int *g,int lenf,int *res)
{
    static int temp[maxn]; int base=power(2,lenf,mod);
    for(int i=0; i<=m; i++)
    {
        temp[i]=0;
        for(int j=0,pow2=1; j<=i; j++,(pow2*=base)%=mod)
            (temp[i]+=c[i][j]*pow2%mod*g[j]%mod*f[i-j]%mod)%=mod;
    }
    for(int i=0; i<=m; i++) res[i]=temp[i];
    return;
}

void solve1()
{
    for(int i=0,j; i<maxn; i++) for(j=1,c[i][0]=1; j<=i; j++) c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
    for(int i=1; i<=m; i++) f[0][i]=mod-1; res[0]=1;
    for(int i=0; i<20; i++) conv(f[i],f[i],1<<i,f[i+1]);
    for(int i=0; i<=20; i++) if((n>>i)&1) conv(f[i],res,1<<i,res);
    if(n&1) res[m]=-res[m];
    cout<<(res[m]%mod+mod)%mod<<'\n';
    return;
}

void solve2()
{
    int tar=0;
    for(int i=0; i<(1<<n); i++)
    {
        int digit=__builtin_popcount(i);
        (tar+=((digit&1)? -1:1)*power(i,m%(mod-1),mod))%=mod;
    }
    if(n&1) tar=-tar;
    return (void)(cout<<((tar%mod+mod)%mod)<<'\n');
}

void work()
{
    /* Code */
    cin>>n>>m;
    if(n>m) return (void)(cout<<0<<'\n');
    if(n<=20) solve2(); else solve1();
    return;
}

signed main()
{
    // file("glass.in","glass.out");
    ios::sync_with_stdio(false); 
    cin.tie(0);
    signed t;
    t=1;
    while(t--)
        work();
    return 0;
} // Texas yyds!!!!

标签：conv,tar,int,res,maxn,酒杯,define
From： https://www.cnblogs.com/ninler/p/18353105