[十二省聯考2019]皮配

題目鏈接

選一個派系和一個陣營可以唯一確定一名導師

因為每一個陣營里的導師都分別來自不同派系，所以k=0時，對陣營的選擇是不影響對派系的選擇的

唯一的限制就是同城市的要在同一個陣營

所以以每個城市為物品，物品大小為該城市的人數，陣營人數為背包容量，做背包dp

再以每個學校為物品，物品大小為該學校的人數，派系人數為背包容量，做背包dp

只用一維記錄背包大小即可，因為總人數-背包里的人數=在另一個陣營或派系的人數

然后合并答案即可

方案數是可以相互乘起來的，k很小，所以我們可以暴力做k！=0的情況，然后乘上符合要求的k==0的方案數

k！=0時，記\(f[x][t][i][j]\)為前x個學校，前一個學校選擇了t陣營，此時藍有i個人，鴨派有j個人的方案數

滾動第一維，否則空間會爆

將學校按城市排序，這樣相同城市的就會排在一起，轉移的時候如果和前一個學校同城就要選擇相同陣營

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
typedef long long ll;
typedef double db;
char cch;
inline int rd(){int x=0,fl=1;cch=getchar();while(cch>'9'||cch<'0'){if(cch=='-') fl=-1;cch=getchar();}while(cch>='0'&&cch<='9') x=(x<<3)+(x<<1)+cch-'0',cch=getchar();return x*fl;
}
const int mod=998244353,N=3000;
struct abc{int ct,sum,ban;
}p1[N],p2[N];
int f[N],g[N],ff[2][2][N][N],ok[N],bl[N],ct[N],city[N],sum[N],ban[N];
inline void inc(int &A,int B){//會比 %mod快一點點 A+=B;if(A>mod) A-=mod;if(A<0) A+=mod;
}
inline int mul(int A,int B){return 1ll*A*B%mod;
}
inline int sub(int a,int b){a-=b;if(a<0) a+=mod;return a;
}
inline int getg(int l,int r){if(l>r) return 0;if(l==0) return g[r];//為了dp方便g[0]=1，實際上應該是0return sub(g[r],g[l-1]);
}
inline int getf(int l,int r){if(l>r) return 0;if(l==0) return f[r];//同理 return sub(f[r],f[l-1]);
}
inline bool cmp(const abc &a1,const abc &a2){return a1.ct<a2.ct;
}
inline void sv(){int n=rd(),c=rd(),c0=rd(),c1=rd(),d0=rd(),d1=rd(),ans=0,tot=0;//n所學校，c個城市，藍陣營 C0。 紅陣營 C1。 鴨派系 D0。 R派系D1。memset(city,0,sizeof city);rep(i,1,n) ct[i]=rd(),sum[i]=rd(),tot+=sum[i],ban[i]=-1,city[ct[i]]+=sum[i];//city[i]表示第i個城市一共有多少人 int k=rd(),id;rep(i,1,k) id=rd(),ban[id]=rd();int len1=0,len2=0;rep(i,1,n){if(ban[i]!=-1) p1[++len1]=(abc){ct[i],sum[i],ban[i]};//有特殊要求的 else p2[++len2]=(abc){ct[i],sum[i],ban[i]};//沒有特殊要求的 }sort(p1+1,p1+len1+1,cmp);//按城市排序rep(i,1,len1){if(city[p1[i].ct]==-1) ok[i]=0;//陣營的轉移以城市為單位else ok[i]=city[p1[i].ct]/*注意*/,city[p1[i].ct]=-1;}//memset(g,0,sizeof g),g[0]=1;rep(i,1,c) if(city[i]>0) for(int j=c0;j>=city[i];--j) inc(g[j],g[j-city[i]]);/*做前綴和*/rep(i,1,c0) inc(g[i],g[i-1]);//memset(f,0,sizeof f),f[0]=1;rep(i,1,len2) for(int j=d0;j>=p2[i].sum;--j) inc(f[j],f[j-p2[i].sum]);/*做前綴和*/rep(i,1,d0) inc(f[i],f[i-1]);//memset(ff,0,sizeof ff);//ff[x][t][i][j]為前x個學校，前一個學校選擇了t陣營，此時藍有i個人，鴨派有j個人的方案數，滾動第一維 ff[0][0][0][0]=1;int cnt=0,now=0;rep(i,1,len1){//對有要求的學校暴力求解now^=1;int tmp=p1[i].sum,bn=p1[i].ban,d=ok[i],lst=cnt;//lst=之前的學校的總人數 cnt+=tmp;rep(t,0,1) rep(h,0,c0) rep(j,0,cnt) ff[now][t][h][j]=0;//這里不可以用memset，用了會超時，因為一開始cnt很小，所以循環更快 rep(t,0,1){int cs=-1;//choiseif(i>1&&p1[i].ct==p1[i-1].ct) cs=t; for(int i=c0;i>=0;--i) for(int j=cnt;j>=0;--j){if(cs!=1){//如果同城市的選擇了0陣營，或與上一個不同城，if(bn!=1&&i>=d&&j<=lst) inc(ff[now][0][i][j],ff[now^1][t]/*注意是t而不是0*/[i-d][j]);//沒有禁掉小R，可以加入R派 if(bn!=0&&i>=d&&j-tmp<=lst&&j>=tmp) inc(ff[now][0][i][j],ff[now^1][t][i-d][j-tmp]);//沒有禁掉Yazid，可以加入鴨派}if(cs!=0){//如果同城市的選擇了1陣營，或與上一個不同城，if(bn!=3&&j<=lst) inc(ff[now][1][i][j],ff[now^1][t][i][j]);if(bn!=2&&j-tmp<=lst&&j>=tmp) inc(ff[now][1][i][j],ff[now^1][t][i][j-tmp]);}}}}//rep(t,0,1) rep(i,0,c0) rep(j,0,d0){int v=ff[now][t][i][j];if(!v)continue;int t1=c0-i,t2=max(0,tot-d1-j),t3=max(0,tot-c1-i),t4=d0-j;//符合人數要求的區間 inc(ans,mul(v,mul(getg(t3,t1),getf(t2,t4))));}printf("%d\n",ans);
}
int main(){int T=rd();while(T--) sv();
}
/*
2
2 1
3 2 2 2
1 1
1 2
1
1 0
4 2
10 30 20 30
1 6
2 4
1 7
2 4
2
2 3
3 1
*/