Luogu

LOJ

分析

首先注意到学校选择导师和选择派系是等价的。

考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立,可以分开处理。

设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数,$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。

统计答案时枚举第二维乘起来累加即可。

考虑 $k\neq 0$ 的情况。注意到有限制的学校数很少,可以单独拿出来处理。

设 $f_{i,j}$ 表示前 $i$ 个没有限制的城市有 $j$ 个人在蓝阵营的方案数,$g_{i,j}$ 表示前 $i$ 所没有限制的学校有 $j$ 个人在鸭派系的方案数。转移仍然为 0/1 背包。

设 $dp_{i,x,y}$ 表示前 $i$ 个有限制的学校有 $x$ 个人在蓝阵营 $y$ 个人在鸭派系的方案数。转移时可以先求出 $F_{x,y}$ 表示当前城市的人全部在蓝阵营且有 $y$ 人在鸭派系的方案数,$G_{x,y}$ 表示当前城市的人全部在红阵营且有 $y$ 人在鸭派系的方案数,然后合并即可。

最后统计答案时枚举有限制学校中选择蓝阵营的人数 $x$ 和选择鸭派系的人数 $y$,则可以计算出没有限制的学校中的人数范围,则将 $f$ 中对应的一段的和乘上 $g$ 中对应的一段的和再乘上 $dp_{?,x,y}$ 累加进答案即可。

实现时需要滚动数组。另外注意可能存在没有人的城市。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2500+10;
const int mod=998244353;

int n,c,k,c0,c1,d0,d1,sum;
int b[N],school_sum[N],hate[N],city_sum[N],have_hate[N];
int f[N],g[N],dp[N][N],F[N][N],G[N][N];

int calc(int x,int y) {
    int i=max(sum-c1-x,0),j=c0-x,k=max(sum-d1-y,0),l=d0-y;
    if (i>j||k>l) return 0;
    return 1ll*(f[j]-f[i-1]+mod)*(g[l]-g[k-1]+mod)%mod;
}

void init() {
    sum=0;
    memset(city_sum,0,sizeof(city_sum));
    memset(hate,-1,sizeof(hate));
    memset(have_hate,0,sizeof(have_hate));
    memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
    memset(dp,0,sizeof(dp)),memset(F,0,sizeof(F)),memset(G,0,sizeof(G));
}

int main() {
    int T=read();
    while (T--) { init();
        n=read(),c=read(),c0=read(),c1=read(),d0=read(),d1=read();
        for (int i=1;i<=n;++i) {
            b[i]=read(),school_sum[i]=read();
            sum+=school_sum[i],city_sum[b[i]]+=school_sum[i];
        }
        k=read();
        for (int i=1;i<=k;++i) {
            int x=read(); hate[x]=read(),have_hate[b[x]]=1;
        }
        
        f[0]=1;
        for (int i=1;i<=c;++i) {
            if (have_hate[i]||!city_sum[i]) continue;
            for (int j=c0;j>=city_sum[i];--j)
                f[j]=(f[j]+f[j-city_sum[i]])%mod;
        }
        for (int i=1;i<=c0;++i) f[i]=(f[i]+f[i-1])%mod;

        g[0]=1;
        for (int i=1;i<=n;++i) {
            if (~hate[i]) continue;
            for (int j=d0;j>=school_sum[i];--j)
                g[j]=(g[j]+g[j-school_sum[i]])%mod;
        }
        for (int i=1;i<=d0;++i) g[i]=(g[i]+g[i-1])%mod;

        dp[0][0]=1; int limx=0,limy=0;
        for (int i=1;i<=c;++i) {
            if (!have_hate[i]) continue;
            for (int x=0;x<=limx;++x)
                for (int y=0;y<=limy;++y)
                    F[x][y]=G[x][y]=dp[x][y];
            for (int j=1;j<=n;++j) {
                if (b[j]!=i||!~hate[j]) continue;
                limy=min(d0,limy+school_sum[j]);
                for (int x=0;x<=limx;++x)
                    for (int y=limy;y>=0;--y) {
                        int ta=(hate[j]!=0)*F[x][y-school_sum[j]];
                        int tb=(hate[j]!=1)*F[x][y];
                        F[x][y]=((y>=school_sum[j]?ta:0)+tb)%mod;
                        int tc=(hate[j]!=2)*G[x][y-school_sum[j]];
                        int td=(hate[j]!=3)*G[x][y];
                        G[x][y]=((y>=school_sum[j]?tc:0)+td)%mod;
                    }

            }
            limx=min(c0,limx+city_sum[i]);
            for (int x=0;x<=limx;++x)
                for (int y=0;y<=limy;++y)
                    dp[x][y]=((x>=city_sum[i]?F[x-city_sum[i]][y]:0)+G[x][y])%mod;
        }
        int ans=0;
        for (int x=0;x<=limx;++x)
            for (int y=0;y<=limy;++y)
                ans=(ans+1ll*dp[x][y]*calc(x,y))%mod;
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2020 年 05 月 03 日 08 : 00 PM