[Gym 102114F]Fireflies

Link

第一步的题意转化就并没想到(根本没往子集的方向去想)
Consider all the lattice points in a hypercube \ { (x_1,x_2,…,x_n)|0\le x_i < p_i \ } . Find a maximal subset such that there are no two points (x_1,x_2,…,x_n),(y_1,y_2,…,y_n) meeting the condition x_i≤y_i for all i. Report its size modulo 10^9+7.

Solution

对于任意集合S,如果它的一个子集集合F满足\forall X,Y\in F,X\not\subset Y,Y\not\subset X,则我们把这样的子集F称为Sperner族。
一个集合的极大Sperner族的元素个数为\binom{|S|}{\lfloor\frac {|S|}{2}\rfloor},是为Sperner定理。达到这个数目只需要取出所有\lfloor\frac {|S|}{2}\rfloor元子集。
Sperner定理可以直接用于解决问题在p_i=2时的情形,将某一位坐标的0,1转化为在集合中的选与不选。

Sperner 定理的一种推广可以给出本问题的答案:选择满足所有坐标之和等于 M = \lfloor \frac{1}{2} \sum_{i = 1}^{n}(p_i-1) \rfloor的位置即可达到最大的数量。

最终问题变成了,求\sum x_i=M,x_i\in[0,p_i)的解数,也就是\sum x_i=M+n,x_i\in[1,p_i]的解数。

由容斥原理,答案为\sum_{T\subset S}(-1)^{|T|}\binom{M-1-\sum_{i\subset T}p_i}{n-1}

使用meet-in-middle策略。
由于\binom{a-x}{b}可以写成一个b次的多项式,而n-1又很小,因此可以处理出左侧集合的关于右侧集合选出元素之和x对答案贡献的多项式的前缀和,枚举右侧集合的元素,然后利用左侧集合多项式的前缀和来处理答案。

\begin{aligned}
&\sum_{T\subset S}(-1)^{|T|}\binom{M-1-\sum_{i\subset T}p_i}{n-1}\\
=&\sum_{T_1\in S_1}\sum_{T_0\in S_0}(-1)^{|T_0|+|T_1|}\binom{M-1-\sum_{i\in T_0}p_i-\sum_{i\in T_1}p_i}{n-1}\\
=&\sum_{T_1\in S_1}(-1)^{|T_1|}\sum_{T_0\in S_0}(-1)^{|T_0|}F(\sum_{i\in T_1}p_i)\\
\end{aligned}

Code

#include <bits/stdc++.h>

const int XN=40,P=1e9+7;

int Pow(long long base,int v) {
    long long res;
    for(res=1;v;v>>=1,(base*=base)%=P)
        if(v&1)
            (res*=base)%=P;
    return res;
}

std::vector<int> Conv(std::vector<int> const &a,std::vector<int> const &b) {
    std::vector<int> c(a.size()+b.size()-1,0);
    for(size_t i=0;i<a.size();++i)
        for(size_t j=0;j<b.size();++j)
            (c[i+j]+=1ll*a[i]*b[j]%P)%=P;
    return c;
}

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);

    freopen("input","r",stdin);

    int ifact[XN]={1};
    for(int i=1;i<XN;++i)
        ifact[i]=1ll*ifact[i-1]*Pow(i,P-2)%P;

    int T;std::cin>>T;

    while(T--) {
        int n;std::cin>>n;
        std::vector<int> p(n),s0,s1;
        long long M=0;
        for(int i=0;i<n;++i) {
            std::cin>>p[i];
            M+=p[i]-1;
            (i<(n+1)/2?s0:s1).push_back(p[i]);
        }
        (M/=2)+=n;
        std::vector<std::pair<long long,int>> v0;
        for(int S=0;S<(1<<s0.size());++S) {
            long long sum=0;
            for(size_t i=0;i<s0.size();++i)
                if(S>>i&1)
                    sum+=s0[i];
            v0.push_back({sum,__builtin_popcount(S)&1?-1:1});
        }
        std::sort(v0.begin(),v0.end());
        std::vector<std::vector<int>> f(v0.size(),std::vector<int>(n,0));
        for(size_t i=0;i<v0.size();++i) {
            std::vector<int> p{1};
            for(int j=0;j<n-1;++j)
                p=Conv(p,{(int)((M-1-v0[i].first-j)%P),-1});//XXX
            for(int &x : p)
                x=1ll*x*ifact[n-1]*v0[i].second%P;
            for(int j=0;j<n;++j)
                f[i][j]=((i?f[i-1][j]:0)+p[j])%P;
        }
        //需要枚举右集合的状态 一下子统计上所有左集合中和+和<=M-1的状态的
        //(-1)^J0 * (-1)^J1*F(X0+X1)
        int Ans=0;
        for(int S=0;S<(1<<s1.size());++S) {
            long long sum=0;
            for(size_t i=0;i<s1.size();++i)
                if(S>>i&1)
                    sum+=s1[i];
            if(sum<=M-1) {
                int p=std::upper_bound(v0.begin(),v0.end(),std::make_pair(M-1-sum,1))-v0.begin()-1,
                    c=__builtin_popcount(S)&1?-1:1;
                int res=0;
                sum%=P;
                for(int i=n-1;i>=0;--i)
                    res=(res*sum+f[p][i])%P;
                (Ans+=c*res)%=P;
            }
        }
        if(Ans<0)
            Ans+=P;
        std::cout<<Ans<<'\n';
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注