LOJ#3051. 「十二省联考 2019」皮配
当时我在考场上觉得这题很不可做。。。
当然，出了考场后再做，我还是没发现学校和城市是可以分开的，导致我还是不会
事实上，若一个城市投靠了某个阵营，学校可以任意选择派系，但是反过来看，学校选择了派系，也不影响城市投靠什么阵营，而这两者共同固定了一个学校选择的导师，所以对于k = 0的情况
我们设两个dp，\(g[i][j]\)表示考虑了前i个城市，去蓝阵营的人数为j，\(h[i][j]\)表示考虑了前i个城市，去鸭派系的人数为j，最后只需要把合法的分别乘起来就好
对于\(k!=0\)的情况，没有限制的城市，和没有限制的学校，都可以按照k = 0的方案去做
然而这些限制给的是什么呢，可以认为是选了一些蓝阵营的城市，将导致我们必须选鸭派系或者必须选R派系，选了红阵营亦然。这个时候两者就有关系了，所以设\(f[i][j][k]\)是考虑了前i个有限制的城市，选了蓝阵营的城市总人数为\(j\)在，在有限制的学校中选了鸭派系的人数是\(k\)
滚动数组就可以开的下了
然后答案合并的时候是会选择g和h一段连续的区间和\(f[i][j][k]\)合并，计算上下界查区间和即可
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define ba 47
//#define ivorysi
#define MAXN 50010
#define MAXM 200005
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
const int MOD = 998244353;
int n,c,k,C0,C1,D0,D1;
vector<int> city[1005];
int f[2505][305],g[2505],h[2505],tmp[305];
int b[1005],s[1005],p[1005],all;
bool lim[1005],dl[1005];
int inc(int a,int b) {
return a + b >= MOD ? a + b - MOD : a + b;
}
int mul(int a,int b) {
return 1LL * a * b % MOD;
}
void update(int &x,int y) {
x = inc(x,y);
}
void Init() {
read(n);read(c);
read(C0);read(C1);read(D0);read(D1);
for(int i = 1 ; i <= c ; ++i) city[i].clear();
memset(lim,0,sizeof(lim));memset(dl,0,sizeof(dl));
all = 0;
for(int i = 1 ; i <= n ; ++i) {
read(b[i]);read(s[i]);all += s[i];
city[b[i]].pb(i);
}
read(k);
int a;
for(int i = 1 ; i <= k ; ++i) {
read(a);read(p[a]);
dl[a] = 1;lim[b[a]] = 1;
}
}
void Solve() {
memset(g,0,sizeof(g));
g[0] = 1;
for(int i = 1 ; i <= c ; ++i) {
if(!lim[i] && city[i].size() > 0) {
int sum = 0;
for(auto t : city[i]) {
sum += s[t];
}
for(int j = C0; j >= sum ; --j) {
update(g[j],g[j - sum]);
}
}
}
memset(h,0,sizeof(h));
h[0] = 1;
for(int i = 1 ; i <= n ; ++i) {
if(!dl[i]) {
for(int j = D0 ; j >= s[i] ; --j) {
update(h[j],h[j - s[i]]);
}
}
}
memset(f,0,sizeof(f));
f[0][0] = 1;
int tot = 0,nl = 0;
for(int i = 1 ; i <= c ; ++i) {
if(lim[i]) {
int sum = 0,s1 = 0;
for(auto t : city[i]) {
sum += s[t];
if(dl[t]) s1 += s[t];
}
tot = tot + sum;tot = min(tot,C0);
nl = nl + s1;nl = min(nl,D0);
for(int j = tot; j >= 0 ; --j) {
for(int r = 0 ; r <= nl ; ++r) tmp[r] = f[j][r];
for(auto t : city[i]) {
if(dl[t]) {
if(p[t] >= 2) {
if(p[t] == 2) continue;
else {
for(int r = nl ; r >= 0 ; --r) {
if(r >= s[t]) tmp[r] = tmp[r - s[t]];
else tmp[r] = 0;
}
}
}
else {
for(int r = nl ; r >= s[t] ; --r) update(tmp[r],tmp[r - s[t]]);
}
}
}
for(int r = 0 ; r <= nl ; ++r) f[j][r] = tmp[r];
if(j >= sum) {
for(int r = 0 ; r <= nl ; ++r) tmp[r] = f[j - sum][r];
for(auto t : city[i]) {
if(dl[t]) {
if(p[t] < 2) {
if(p[t] == 0) continue;
else {
for(int r = nl ; r >= 0 ; --r) {
if(r >= s[t]) tmp[r] = tmp[r - s[t]];
else tmp[r] = 0;
}
}
}
else {
for(int r = nl ; r >= s[t] ; --r) update(tmp[r],tmp[r - s[t]]);
}
}
}
for(int r = 0 ; r <= nl ; ++r) update(f[j][r],tmp[r]);
}
}
}
}
for(int i = 1 ; i <= C0 ; ++i) update(g[i],g[i - 1]);
for(int i = 1 ; i <= D0 ; ++i) update(h[i],h[i - 1]);
int ans = 0;
for(int i = 0 ; i <= C0 ; ++i) {
for(int j = 0 ; j <= 300 ; ++j) {
int t0 = 0,t1 = 0;
int u = C0 - i,d = all - C1 - i;
if(d <= u) {
t0 = g[u];
if(d > 0) update(t0,MOD - g[d - 1]);
}
u = D0 - j,d = all - D1 - j;
if(d <= u) {
t1 = h[u];
if(d > 0) update(t1,MOD - h[d - 1]);
}
update(ans,mul(f[i][j],mul(t0,t1)));
}
}
out(ans);enter;
cerr << ans;
}
int main(){
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
int T;
read(T);
for(int i = 1 ; i <= T ; ++i) {
Init();
Solve();
}
}