P5289皮配题解

题面过于复杂，有一个显然的想法就是让导师们去找学生，设$f(i,j,k,p)$ 表示四个导师选的人数状态下的方案数，转移判断满不满足题目中所给的派系和阵营限制即可，时间复杂度$O(nm^4)$，不难发现只需要确定三个即可，时间复杂度$O(nm^3)$。然后就不会了。

观察这个 DP 及其难以优化，因为如果我们缺任何一个信息都无法描述完整的子问题，而且复杂度要求的可是$O(nm)$，你只知道一个信息那么肯定啥也导出不了啊。我们考虑发掘几个性质：

• 确定一个派系和一个阵营可以唯一确定一位导师。
• 题目中 ban 导师的相当于不选钦定的派系和阵营。

上述性质启示我们让每一个学生去确定它们的派系和阵营，而不是导师去确定学生。但是还有我们的 “坏” 学生，不喜欢选的。我们先丢掉它们，先考虑$k=0$ 的部分分。

有一个显然的 DP 就是$f(i,j)$ 表示$i$ 个蓝阵营的人，$j$ 个鸭阵营的人的方案数，剩余两个可以由这两个状态唯一表示出来，时间复杂度$O(nm^2)$，仍无法通过。正解启示$O(nm)$，考虑进一步发掘性质：

• 题目中学生来自的城市限制，和学校限制是互相独立互不冲突的。

这个性质启发我们分离上面状态设计中的$i,j$。那么不妨设$f(i)$ 表示蓝阵营有$i$ 个人的方案数，$g(i)$ 表示鸭阵营有$i$ 个人的方案数，两个答案可以通过乘法原理分别算出来之后乘起来即可，时间复杂度$O(nm)$。

现在考虑$k>0$，一个重要的观察是$k\le 30$。状压、枚举？都不对。我们上面的计算答案过程中体现了乘法原理的思想，也就是说我们也可以分离 “坏学生” 和 “好学生”，好学生单独做，坏学生单独做，最后乘起来即可。

坏学生的限制怎么处理，我们肯定不能用$O(nm)$ 的算法了，这个算法肯定是无法处理我们的限制的。回看我们之前$O(nm^2)$ 的解法，这个就能够很好的处理性质，因为状态能够表示所有派系阵营选择人数，我们可以用这个算法处理坏学生就可以啦。时间复杂度做的话是$O(k^2sm)$ 的。

那么时间复杂度就是$O(nm+k^2 sm)$。

总结：

• 我们在设计状态的时候，应当尽量个限制紧密贴合。在优化 DP 的时候我们要考虑我们计算贡献具体需要什么信息，我们需要什么信息就足够了，去掉冗余的无用信息。
• 题目可能会故意引导你走向死路，如果一个方向想不通，不妨正难则反或换一种方法想，这里体现的是正难则反的思路。

#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=2520,MOD=998244353;
int F[MN][MN],G[MN][MN],f[MN],g[MN],h[MN],s[MN],b[MN],sumb[MN],sums,n,c,c0,c1,d0,d1,C,K,D,ans;
bool hc[MN];

void init(){
    memset(F,0,sizeof(F));
    memset(G,0,sizeof(G));
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    ans=C=D=0; sums=0;
    for(int i=1;i<=n;i++){
        h[i]=-1;
        sumb[i]=0;
        hc[i]=false;
    }
}

void solve(){
    cin>>n>>c>>c0>>c1>>d0>>d1;
    init();
    for(int i=1;i<=n;i++){
        cin>>b[i]>>s[i];
        sums+=s[i];
        sumb[b[i]]+=s[i];
    }
    cin>>K;
    for(int i=1;i<=K;i++){
        int x;cin>>x>>h[x];
        hc[b[x]]=true;
    }
    f[0]=1;
    for(int i=1;i<=c;i++) if(!hc[i]&&sumb[i]){
        for(int j=c0;j>=sumb[i];j--) f[j]=(f[j]+f[j-sumb[i]])%MOD;
    }
    for(int i=1;i<=c0;i++) f[i]=(f[i-1]+f[i])%MOD;
    g[0]=1;
    for(int i=1;i<=n;i++) if(h[i]==-1){
        for(int j=d0;j>=s[i];j--) g[j]=(g[j]+g[j-s[i]])%MOD;
    }
    for(int i=1;i<=d0;i++) g[i]=(g[i-1]+g[i])%MOD;
    F[0][0]=1;
    for(int ct=1;ct<=c;ct++) if(hc[ct]){
        C+=sumb[ct]; C=min(C,c0);
        for(int i=0;i<=C;i++) for(int j=0;j<=D;j++) G[i][j]=F[i][j];
        for(int x=1;x<=n;x++) if(h[x]!=-1&&b[x]==ct){
            int t=s[x]; D+=t; D=min(D,d0);
            if(h[x]==1){ 
                for(int i=0;i<=C;i++){for(int j=D;j>=t;j--) F[i][j]=F[i][j-t]; for(int j=0;j<t;j++) F[i][j]=0;}
            }
            if(h[x]>=2){ 
                for(int i=0;i<=C;i++) for(int j=D;j>=t;j--) F[i][j]=(F[i][j]+F[i][j-t])%MOD;
            }
            if(h[x]==3){ 
                for(int i=0;i<=C;i++){for(int j=D;j>=t;j--) G[i][j]=G[i][j-t]; for(int j=0;j<t;j++) G[i][j]=0;}
            }
            if(h[x]<=1){ 
                for(int i=0;i<=C;i++) for(int j=D;j>=t;j--) G[i][j]=(G[i][j]+G[i][j-t])%MOD;
            }
        }
        int t=sumb[ct];
        if(t>0){
            for(int i=C;i>=t;i--) for(int j=0;j<=D;j++) F[i][j]=F[i-t][j];
            for(int i=0;i<t;i++) for(int j=0;j<=D;j++) F[i][j]=0;
        }
        for(int i=0;i<=C;i++) for(int j=0;j<=D;j++) F[i][j]=(F[i][j]+G[i][j])%MOD;
    }
    for(int i=0;i<=C;i++) for(int j=0;j<=D;j++){
        int l1=max(0ll,sums-c1-i),r1=c0-i; if(l1>r1) continue;
        int l2=max(0ll,sums-d1-j),r2=d0-j; if(l2>r2) continue;
        int ret1=f[r1],ret2=g[r2];
        if(l1) ret1=(ret1-f[l1-1]+MOD)%MOD;
        if(l2) ret2=(ret2-g[l2-1]+MOD)%MOD;
        ans=(ans+ret1*ret2%MOD*F[i][j])%MOD;
    }
    cout<<(ans+MOD)%MOD<<'\n';
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T;cin>>T;while(T--) solve();
    return 0;
}