#loj3051 [十二省联考2019] 皮配-白红宇

#loj3051 [十二省联考2019] 皮配

阅读量：4467 次

发布时间：2019-06-08

本文共 3666 字，大约阅读时间需要 12 分钟。

垃圾yazid毁我青春费我钱财

这题不难就是题面太长概念太多，根本记不住什么变量是什么变量

稍微转化一下发现蓝阵营和鸭派系的人数必须在一个区间当中

如果k=0显然两维相互独立直接背包乘起来就行了

如果k不等于0那么受影响的城市体积之和少于2500，受影响的学校体积之和小于300

那么设\(dp(i,j)\)表示在蓝阵营有体积和为i的被影响城市，鸭派系有体积和为j的被影响学校时

的方案数是什么

转移的时候需要把枚举每个受影响的城市选择哪个阵营，然后跑一个小的背包用来计算城市中的学校选择派系的方案数

有了小的背包数组就可以更新dp数组了

这部分的复杂度是\(O(ms^2k^2)\)的

剩下的部分就很简单了，对于剩下的城市和人分别跑个背包就行了

\(O(nm)\)

然后枚举受影响的城市中有几个选择了蓝阵营，受影响的学校中有几个选择了鸭派系

然后此时在另外两个背包数组上查一下区间和就能解决问题了

总复杂度\(O(nm+ms^2k^2)\)

// luogu-judger-enable-o2#include
    
     #include
     
      #include
      #include
       
         using namespace std;const int N=3*1e4+10;const int M=2530;typedef long long ll;typedef vector 
        
          :: iterator VIT;const ll mod=998244353;inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;}struct stu{    int siz;int ban;};struct backpack{    ll dp[N];int lim;    inline void clear()    {        for(int i=1;i<=2500;i++)dp[i]=0;        lim=0;dp[0]=1;    }    backpack(){lim=0;dp[0]=1;}    inline ll& operator [](const int& x){return dp[x];}    inline void ins_all(int siz)    {        for(int i=lim+1;i<=lim+siz;i++)dp[i]=0;        lim+=siz;        for(int i=lim;i>=siz;i--)            (dp[i]+=dp[i-siz])%=mod;    }    inline void ins_shif(int siz)    {        for(int i=lim+1;i<=lim+siz;i++)dp[i]=0;        lim+=siz;        for(int i=lim;i>=siz;i--)            dp[i]=dp[i-siz];        for(int i=0;i
         
           ver[N]; inline void clear() { for(int i=1;i<=c;i++)ver[i].clear(); for(int i=0;i<=key0;i++) for(int j=0;j<=key1;j++)p[i][j]=0; key0=0;key1=0; } inline void ins(vector 
          
            ve,int tot) { backpack cur0;backpack cur1; for(vector 
           
             :: iterator it=ve.begin();it!=ve.end();++it) if(it->ban==1)cur0.ins_shif(it->siz); else if(it->ban!=0)cur0.ins_all(it->siz); for(vector 
            
              :: iterator it=ve.begin();it!=ve.end();++it) if(it->ban==3)cur1.ins_shif(it->siz); else if(it->ban!=2)cur1.ins_all(it->siz); key0+=tot;key1+=max(cur0.lim,cur1.lim);key0=min(key0,c0); for(int i=0;i<=key0;i++) for(int j=0;j<=key1;j++)q[i][j]=0; for(int i=0;i<=key0;i++) for(int j=0;j<=key1;j++) if(p[i][j]) { ll tmp=p[i][j]; for(int k=0;k<=cur0.lim&&j+k<=key1;k++) (q[i+tot][j+k]+=cur0[k]*tmp)%=mod; for(int k=0;k<=cur1.lim&&j+k<=key1;k++) (q[i][j+k]+=cur1[k]*tmp)%=mod; } for(int i=0;i<=key0;i++) for(int j=0;j<=key1;j++) p[i][j]=q[i][j]; } inline void solve() { p[0][0]=1; for(int i=1;i<=c;i++) if(ver[i].size()!=0)ins(ver[i],colsiz[i]); ll ans=0; for(int i=0;i<=key0;i++) { ll sum=0; for(int j=0;j<=key1;j++) if(p[i][j]) (sum+=p[i][j]*bpl.gsum(lstl-i,lstr-i)%mod*bpf.gsum(fstl-j,fstr-j))%=mod; (ans+=sum)%=mod; } printf("%lld\n",ans); } }inline void clear(){ for(int i=1;i<=n;i++)colsiz[i]=0; for(int i=1;i<=n;i++)bookc[i]=false; for(int i=1;i<=n;i++)bookid[i]=false; bpf.clear();bpl.clear(); solver1::clear(); n=0;c=0;c0=0;c1=0;d0=0;d1=0; fstl=0;fstr=0;lstl=0;lstr=0;}inline void solve(){ scanf("%d%d",&n,&c); scanf("%d%d%d%d",&c0,&c1,&d0,&d1); int b[N];int s[N];int tot=0; for(int i=1;i<=n;i++) scanf("%d%d",&b[i],&s[i]),tot+=s[i]; int k; scanf("%d",&k); for(int i=1,t,typ;i<=k;i++) scanf("%d%d",&t,&typ), bookc[b[t]]=true,bookid[t]=true, solver1::ver[b[t]].push_back((stu){s[t],typ}); for(int i=1;i<=n;i++) colsiz[b[i]]+=s[i]; bpl[0]=1;bpf[0]=1; for(int i=1;i<=c;i++) if(colsiz[i]&&bookc[i]==false) bpl.ins_all(colsiz[i]),bpl.lim=min(bpl.lim,c0); for(int i=1;i<=n;i++) if(bookid[i]==false) bpf.ins_all(s[i]),bpf.lim=min(bpf.lim,d0); bpl.pre();bpf.pre(); fstr=d0;fstl=max(tot-d1-1,-1); lstr=c0;lstl=max(tot-c1-1,-1); solver1::solve();}int main(){ int T; scanf("%d",&T); for(int z=1;z<=T;z++) solve(),clear(); return 0;}