题目链接
题目解法
题意比较复杂，形式化一下题意是：
一些人和一些城市，每个人属于一个城市，每个人属于 \(A/B/C/D\) 队，需要满足：每个城市中的人要么都属于 \(AC\) 或 \(BD\)，且 \(A+C\le C_0,\;B+D\le C_1,\;A+B\le D_0,\;C+D\le D_1\)
暴力 \(dp\) 是 \(f_{i,a,b,c}\) 表示到第 \(i\) 个城市，\(A,B,C\) 集合中有几个人的方案数，是 \(O(n^5)\) 的
这样显然是没有必要的，因为题目只限制了两数之和。所以令 \(f_{i,j,k}\) 为到第 \(i\) 个城市，\(AB\) 集合中一共有 \(j\) 个人，\(AC\) 集合中一共有 \(k\) 个人的方案数，不难 \(O(n^4)\) 转移
首先考虑 \(k=0\) 的情况
一个发现是：每个人属于 \(AC\) 与 \(BD\) 集合 与 属于 \(AB\) 和 \(CD\) 集合的方案数是独立的
即每个人可以先选择加入 \(AC\) 或 \(BD\)，再选择 \(AB\) 和 \(CD\)，贡献是独立的，可以分别计算然后累乘
这不难 \(dp\) 求解
考虑推广到 \(k>0\) 的情况
观察到 \(k\le 30\)，考虑对于每个有限制的人的城市，单独计算
没有限制的城市直接按照 \(k=0\) 的处理方式即可
发现对于 \(AB\) 和 \(CD\) 一维，人与城市是独立的，所以可以把 城市有限制 但 人没有限制 的在 \(k=0\) 的 \(dp\) 中一并求解
然后就可以用暴力 \(dp\) 的方法求解，可以发现 \(j\le M(2500),\le k\le 300(10k)\)，所以暴力做是 ok 的
时间复杂度 \(O(nm+10k^2m)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int N=1100,P=998244353,K=32,M=2510;
int n,c,C0,C1,D0,D1,k;
int f[M],g[M],h[M][K*10],tmp[M][K*10];
int b[N],s[N],hate[N];
vector<pii> city[N];
int cnt[4];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int calc(int *a,int l,int r){
if(l>r||r<0) return 0;
l=max(l,0);
if(!l) return a[r];
else return (a[r]-a[l-1]+P)%P;
}
void work(){
n=read(),c=read(),C0=read(),C1=read(),D0=read(),D1=read();
int tot=0;
F(i,1,n) b[i]=read(),s[i]=read(),tot+=s[i];
k=read();
ms(hate,-1);
F(i,1,k){ int x=read();hate[x]=read();if(hate[x]==1||hate[x]==2) hate[x]=3-hate[x];}
F(i,1,n) city[b[i]].pb({s[i],hate[i]});
ms(g,0),ms(f,0),ms(h,0);
int bound1=0,bound2=0,bound3=0,bound4=0;
g[0]=f[0]=h[0][0]=1;
F(i,1,n){
if(city[i].empty()) continue;
int addsz=0;
bool flg=false;
for(auto [siz,hate]:city[i]){
addsz+=siz;
if(hate!=-1) flg=true,bound4+=siz;
else{ bound1=min(bound1+siz,M-1);DF(j,bound1,siz) inc(g[j],g[j-siz]);}
}
if(!flg){ bound2=min(bound2+addsz,M-1);DF(j,bound2,addsz) inc(f[j],f[j-addsz]);continue;}
bound3=min(bound3+addsz,M-1),chkmin(bound4,M-1);
F(j,0,bound3) F(k,0,bound4) tmp[j][k]=h[j][k];
for(auto [siz,hate]:city[i]){
if(hate==2) DF(j,bound3,siz) DF(k,bound4,siz) h[j][k]=h[j-siz][k-siz],h[j-siz][k-siz]=0;
else if(hate==0||hate==-1) DF(j,bound3,siz) DF(k,bound4,0) h[j][k]=h[j-siz][k],h[j-siz][k]=0;
else DF(j,bound3,siz) DF(k,bound4,0){
h[j][k]=h[j-siz][k],h[j-siz][k]=0;
if(k>=siz) inc(h[j][k],h[j-siz][k-siz]);
}
}
for(auto [siz,hate]:city[i]){
if(hate==1||hate==-1) ;
else if(hate==3) DF(j,bound3,0) DF(k,bound4,siz) tmp[j][k]=tmp[j][k-siz],tmp[j][k-siz]=0;
else DF(j,bound3,0) DF(k,bound4,siz) inc(tmp[j][k],tmp[j][k-siz]);
}
F(j,0,bound3) F(k,0,bound4) inc(h[j][k],tmp[j][k]);
}
F(i,1,M-1) inc(f[i],f[i-1]),inc(g[i],g[i-1]);
int ans=0;
F(i,0,M-1) F(j,0,K*10-1) if(h[i][j]) inc(ans,1ll*h[i][j]*calc(f,tot-i-C1,C0-i)%P*calc(g,tot-j-D1,D0-j)%P);
printf("%d\n",ans);
F(i,1,n) city[i].clear();
}
int main(){
int T=read();
while(T--) work();
return 0;
}