[十二省联考 2019] 皮配

LOJ #3051.

假如没有$k$个不能选的限制,整个问题可以拆成两个不相互影响的问题——给每个城市确定一个阵营,给每个学校确定一个派系。然后乘法原理直接乘起来就可以了。

现在出现了$K$个限制,但是$K\leq 30$,所以对于$K$个学校可以暴力DP。对于有带限制的学校的城市,先给整个城市分配一下阵营,再给每个学校分配一下派系。再给没有带限制的学校的城市分配阵营,给不带限制的学校分配派系,乘起来就可以了

#include <iostream>
#include <cstdio>
#include <cstring>

template <typename T> void in(T &_){
    char c=getchar(); _=0; int fl=1;
    while(c<'0'||c>'9') fl=c=='-'?-1:fl, c=getchar();
    while(c>='0'&&c<='9') _=_*10+c-'0', c=getchar(); _*=fl;
}
template <typename T, typename ...A> void in(T &_, A &...a){
    in(_); in(a...);
}

const int MOD=998244353;

int n, c, C0, C1, D0, D1, tot;
int b[1010], s[1010], sc[1010], ban[1010], f1[2510], f2[2510], f[2510][2510][2];
bool fl[1010];

int calc(int x, int y){
    int res=1, lim=tot-C1-x;
    if(lim>C0-x) return 0;
    res=1ll*(f2[C0-x]-(lim>0?f2[lim-1]:0))%MOD*res%MOD;
    lim=tot-D1-y;
    if(lim>D0-y) return 0;
    res=1ll*(f1[D0-y]-(lim>0?f1[lim-1]:0))%MOD*res%MOD; 
    return res;
}

int main(){
    int T, K, x, y; in(T);
    while(T--){
        memset(fl, 0, sizeof(fl));
        memset(ban, -1, sizeof(ban));
        memset(f, 0, sizeof(f));
        memset(f1, 0, sizeof(f1));
        memset(f2, 0, sizeof(f2));
        memset(sc, 0, sizeof(sc));
        tot=0;
        in(n, c, C0, C1, D0, D1);
        for(int i=1; i<=n; i++){
            in(b[i], s[i]);
            tot+=s[i], sc[b[i]]+=s[i];
        }
        in(K);
        while(K--){
            in(x, y);
            ban[x]=y, fl[b[x]]=true;
        }
        f1[0]=1;
        for(int i=1, sum=0; i<=n; i++) if(ban[i]<0){
            sum+=s[i];
            for(int j=D0; ~j; j--){
                if(sum-j>D1) f1[j]=0;
                if(j>=s[i]) f1[j]=(f1[j]+f1[j-s[i]])%MOD;
            }
        }
        for(int i=1; i<=D0; i++) f1[i]=(f1[i]+f1[i-1])%MOD;
        f2[0]=1;
        for(int i=1, sum=0; i<=c; i++) if(!fl[i] && sc[i]){
            sum+=sc[i];
            for(int j=C0; ~j; j--){
                if(sum-j>C1) f2[j]=0;
                if(j>=sc[i]) f2[j]=(f2[j]+f2[j-sc[i]])%MOD;
            }
        }
        for(int i=1; i<=C0; i++) f2[i]=(f2[i]+f2[i-1])%MOD;
        f[0][0][0]=1;
        for(int i=1, sum=0, s1=0; i<=c; i++) if(fl[i]){
            sum+=sc[i];
            for(int j=C0; ~j; j--){
                if(sum-j>C1) 
                    for(int k=0; k<=std::min(s1, D0); k++) 
                        f[j][k][0]=f[j][k][1]=0;
                else 
                    for(int k=0; k<=std::min(s1, D0); k++) 
                        f[j][k][1]=(f[j][k][0]+f[j][k][1])%MOD, f[j][k][0]=0;
                if(j>=sc[i]) 
                    for(int k=0; k<=std::min(s1, D0); k++) 
                        f[j][k][0]=(f[j-sc[i]][k][0]+f[j-sc[i]][k][1])%MOD;
            }
            for(int j=1; j<=n; j++) if(b[j]==i && ban[j]!=-1){
                s1+=s[j];
                for(int k=std::min(s1, D0); ~k; k--){
                    if(ban[j]==1 || s1-k>D1)
                        for(int w=0; w<=C0; w++) f[w][k][0]=0;
                    if(ban[j]==3 || s1-k>D1)
                        for(int w=0; w<=C0; w++) f[w][k][1]=0;
                    if(ban[j]!=0 && k>=s[j])
                        for(int w=0; w<=C0; w++)
                            f[w][k][0]=(f[w][k][0]+f[w][k-s[j]][0])%MOD;
                    if(ban[j]!=2 && k>=s[j])
                        for(int w=0; w<=C0; w++)
                            f[w][k][1]=(f[w][k][1]+f[w][k-s[j]][1])%MOD;
                }
            }
        }
        int ans=0;
        for(int i=0; i<=C0; i++)
            for(int j=0; j<=D0; j++) if(f[i][j][0] || f[i][j][1])
                ans=(ans+1ll*(f[i][j][0]+f[i][j][1])%MOD*calc(i, j)%MOD)%MOD;
        printf("%d\n", (ans+MOD)%MOD);
    }
    return 0;
}

发表评论

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