假如没有$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;
}