[LuoguP5289] [12성 연합고사 2019] 가죽

제목 링크

제목 설명


대략

Sol


질문
우선 폭력적인 방법은 dp[i][j][k]dp[i][j][k]dp[i][j][k]를 설정한다. 이는 전 ii 도시의 학교가 제1진영 jj인 제1문파 kk인으로 나누어지는 방안 수를 나타낸다.
중간의 한 도시에 있는 학교는 그 진영에 나눠서 01배낭 dp로 문파를 만들면 됩니다.
그리고 dp의 최적화 공간이 없는 것 같다.
k=0k=0k=0을 알아차렸을 때 한 학교가 한 진영에 분배된 후에 공헌할 수 있는 문파는 분배된 진영의 영향을 받지 않는다.그래서 우리는 먼저 모든 k=0k=0k=0의 학교에 문파를 분배할 수 있다. 이것이 바로 01배낭이고 그 다음에 진영의 문제를 고려할 수 있다.
한 도시가 같은 진영으로 나뉘어야 하기 때문에 한 도시의 모든 학교를 함께 고려해야 한다.
왜냐하면k≠0keq0k̸=0의 학교는 최대 3030개에 불과하지만 한 학교의 인원은 최대 1010개에 달하기 때문에 이 부분의 방안은 우리가 최초의 폭력 dp의 방법으로 직접 계산할 수 있다.
이때 우리는 우리가 도대체 어떤 방안을 계산해 냈는지 똑똑히 정리해야 한다.우선 우리 뒷부분의 폭력 dp는 모든 제한된 도시를 위한 진영 분배와 제한된 학교의 문파 분배를 구했다.이전에는 모든 k=0k=0k=0의 도시의 문파 분배도 계산해 냈다.그래서 무제한 도시 진영 분배 방안 수를 계산하면 돼요. 이게 01가방이에요.
그리고 정답을 어떻게 합치죠?우리는 이미 방안을 세 부분으로 나누었다.
  • 무제한 도시의 사람들의 진영 분배
  • 무제한 학교의 문파 분배
  • 기타 모든 사람의 문파 & 진영 분배
  • 우리가 세 번째 부분의 방안에 상기 두 가지 방안을 합치면 먼저 진영을 합치면 문제가 없을 것이다. 왜냐하면 두 부분은 관계가 없기 때문이다.그리고 무제한 학교의 문파 분배 방안을 합쳤다. 우리는 모든 도시의 진영이 합법적이고 진영과 문파가 독립적이기 때문에 합법적이다.
    접두사와 마지막으로 답안을 합치는 과정을 최적화하면 된다.
    code:
    #include
    using namespace std;
    #define Set(a,b) memset(a,b,sizeof(a))
    template<class T>inline void init(T&x){
    	x=0;char ch=getchar();bool t=0;
    	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
    	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
    	if(t) x=-x;return;
    }typedef long long ll;
    const int mod=998244353;
    const int N=1020;
    const int MAXN=2601;
    template<class T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;}
    template<class T>inline void Dec(T&x,int y){x-=y;if(x < 0 ) x+=mod;}
    inline int Sum(int x,int y){x+=y;if(x>=mod) x-=mod;return x;}
    inline int Dif(int x,int y){x-=y;if(x < 0 ) x+=mod;return x;}
    template<class T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
    vector<int> city[N];
    struct school{
    	int idc;int s;int hate;
    	school(int _id=0,int _s=0,int _hate=-1){idc=_id,s=_s;hate=_hate;}
    }P[N];
    int C0,C1,D0,D1,c,curf=0,curg=0,sum=0,n;
    int f[2][MAXN],g[2][MAXN];
    int dp[MAXN][MAXN],F[MAXN][MAXN],G[MAXN][MAXN];
    bool limcity[N];
    inline int Calc(int i,int j){
    	int lei=max(0,sum-i-C1),lej=max(0,sum-j-D1);// least
    	int rei=C0-i,rej=D0-j;// most
    	if(lei>rei||lej>rej) return 0;
    	return (ll)Dif(f[curf][rei],(lei? f[curf][lei-1]:0))*Dif(g[curg][rej],(lej? g[curg][lej-1]:0))%mod;
    }
    int main()
    {
    	int k,T;init(T);
    	while(T--) {
    		Set(f,0),Set(g,0),Set(dp,0),Set(F,0),Set(G,0);curf=curg=sum=0;
    		init(n),init(c);for(int i=1;i<=c;++i) city[i].clear(),limcity[i]=0;
    		init(C0),init(C1),init(D0),init(D1);
    		for(int i=1;i<=n;++i){P[i]=school();init(P[i].idc),init(P[i].s);city[P[i].idc].push_back(i);}
    		init(k);
    		for(int i=1;i<=k;++i){int pe,p;init(pe),init(p);P[pe].hate=p;limcity[P[pe].idc]=1;}
    		f[curf][0]=g[curg][0]=1;
    		for(int i=1;i<=c;++i) {
    			if(!city[i].size()) continue;
    			int SP=0;
    			for(int v:city[i]) {
    				school S=P[v];int s=S.s;
    				if(S.hate!=-1) continue;SP+=s;
    				sum+=s;curg^=1;int ed=min(sum,D0);
    				for(int i=0;i<=ed;++i){
    					g[curg][i]=0;
    					Inc(g[curg][i],g[curg^1][i]);
    					if(i>=s) Inc(g[curg][i],g[curg^1][i-s]);
    				}
    			}if(limcity[i]) continue;
    			curf^=1;int ed=min(sum,C0);
    			for(int i=0;i<=ed;++i){
    				f[curf][i]=0;
    				Inc(f[curf][i],f[curf^1][i]);
    				if(i>=SP) Inc(f[curf][i],f[curf^1][i-SP]); 
    			}
    		}int nows=0;dp[0][0]=1;
    		for(int i=1;i<=C0;++i) Inc(f[curf][i],f[curf][i-1]);
    		for(int i=1;i<=D0;++i) Inc(g[curg][i],g[curg][i-1]);
    		for(int i=1;i<=c;++i) {
    			if(!city[i].size()) continue;
    			if(!limcity[i]) continue;
    			int SP=0,SS=0;
    			int ed1=min(C0,nows),ed2=min(D0,nows);
    			for(int j=0;j<=ed1;++j)for(int k=0;k<=ed2;++k) F[j][k]=G[j][k]=dp[j][k];
    			for(int v:city[i]) {
    				school S=P[v];int s=S.s;SP+=s;
    				if(S.hate==-1) continue;
    				else{
    					nows+=s;SS+=s;sum+=s;
    					ed1=min(C0,nows);
    					ed2=min(D0,nows);
    					for(int j=ed1;~j;--j){
    						for(int k=ed2;~k;--k){
    							F[j][k]=0;
    							if(S.hate!=0&&j>=s&&k>=s) Inc(F[j][k],F[j-s][k-s]);//C0
    							if(S.hate!=1&&j>=s) Inc(F[j][k],F[j-s][k]);
    							if(S.hate==3) G[j][k]=0;
    							if(S.hate!=2&&k>=s) Inc(G[j][k],G[j][k-s]);// C1
    						}
    					}
    				}
    			}int SG=SP-SS;// more
    			nows+=SG;ed1=min(C0,nows),ed2=min(D0,nows);
    			for(int j=0;j<=ed1;++j)
    				for(int k=0;k<=ed2;++k) {
    					//  F[j][k]  -->  dp[j+SG][k] C0
    					//  G[j][k]  -->  dp[j   ][k] C1
    					dp[j][k]=0;
    					if(j>=SG) Inc(dp[j][k],F[j-SG][k]);
    					Inc(dp[j][k],G[j][k]);
    				}
    		}int ans=0;
    		for(int j=0;j<=C0;++j) for(int k=0;k<=D0;++k) Inc(ans,(ll)dp[j][k]*Calc(j,k)%mod);
    		cout<<ans<<endl;
    	}
    	return 0;
    }
    
    

    좋은 웹페이지 즐겨찾기