[TJOI2019]唱、跳、rap和篮球

ゝ一世哀愁。 2022-01-12 10:49 176阅读 0赞

[\[TJOI2019\]唱、跳、rap和篮球][TJOI2019_rap]

律师函警告

考虑容斥，减去至少一个cxk的

枚举有i个cxk，方案数：C(n-3\*i,i)因为不相交，所以直接扣掉剩下3个，选择第一个开始的位置，一一对应

剩下的？随便，统计多了？

二项式反演！

需要计算：(a-i,b-i,c-i,d-i,n-4\*i)

表示用a-i,b-i,c-i,d-i,填n-4\*i的队列的不同方案数。

指数生成函数搞定。

O(4\*500log500\*(1000/4))

const int N=1005;
    int n,t[4];
    int h[N],f[N],g[N];
    ll ans;
    int jie[N],inv[N];
    int C[N][N];
    int calc(int p){
        int goal=n-4*p;
        // cout<<" calc "<<p<<" goal "<<goal<<endl;
        // cout<<"324354 "<<endl;
        Poly ret;ret.resize(1);ret[0]=1;
    
        for(reg i=0;i<4;++i){
            // cout<<" iii "<<i<<endl;
            Poly tmp;tmp.resize(t[i]-p+1);
            // cout<<" resize "<<endl;
            for(reg j=0;j<t[i]-p+1;++j){
                tmp[j]=inv[j];
            }
            // tmp.out();
            ret=ret*tmp;
            // cout<<" after i "<<i<<endl;
            ret.resize(min(ret.size(),goal+1));
            // ret.out();
        }
        return mul(jie[goal],ret[goal]);
    }
    int main(){
        rd(n);
        int lim=n/4;
        for(reg i=0;i<4;++i) rd(t[i]),lim=min(lim,t[i]);
    
        jie[0]=1;
        for(reg i=1;i<=N-3;++i) jie[i]=mul(jie[i-1],i);
        inv[N-3]=qm(jie[N-3],mod-2);
        for(reg i=N-4;i>=0;--i) inv[i]=mul(inv[i+1],i+1);
        C[0][0]=1;
        for(reg i=1;i<=N-3;++i){
            C[i][0]=1;
            for(reg j=1;j<=i;++j){
                C[i][j]=ad(C[i-1][j],C[i-1][j-1]);
            }
        }
        // cout<<" C,jie,inv"<<endl;
        // prt(jie,0,20);
        // prt(inv,0,20);
        for(reg i=0;i<=lim;++i){
            h[i]=calc(i);
        }
        // prt(h,0,lim);
    
        for(reg i=1;i<=lim;++i){
            f[i]=mul(C[n-3*i][i],h[i]);
        }
        ll sum=0;
        for(reg i=1;i<=lim;++i){
            ll now=0;
            for(reg j=i;j<=lim;++j){
                if((j-i)&1){
                    now=ad(now,mod-mul(f[j],C[j][i]));
                }else{
                    now=ad(now,mul(f[j],C[j][i]));
                }
            }
            sum=ad(sum,now);
        }
        ans=ad(h[0],mod-sum);
        ot(ans);
        return 0;
    }

转载于:https://www.cnblogs.com/Miracevin/p/10851700.html

[TJOI2019_rap]: https://www.luogu.org/problemnew/show/P5339