kmjp's blog

競技プログラミング参加記です

Codeforces #1121 : Div2. E2. A Prime Flood (Hard Version)

なるほど…。
https://codeforces.com/contest/2264/problem/E2

問題

整数列Bに対し、f(B)は以下で作れる最大の整数を示す。

  • 素数pを選ぶ。Bのうちpの倍数のものは1減らす。
  • 上記をBの全要素が一致するまで繰り返す。

整数列Aが与えられる。Aの空でない部分列をBとすると、その2^|A|-1通りのBにおけるf(B)の総和を求めよ。

解法

Bの最小値をL、最大値をRとすると、LとRが一致する過程で(L+1)以上(R-1)以下の値も同じ値になっていく。
そのため、Bで考えるべきは最大値と最小値だけである。

g(L,R) := 最小値L、最大値Rの数列Bに対するf(B)の値
とする。

  • g(x,x) = x
  • Rを構成する素因数が、Lを構成する素因数の部分集合の場合、Rを減らすとLも減るのでg(L,R)=g(L-1,R-1)
  • そうでないとき、g(L,R)=g(L,R-1)

g(L,R)=g(L-1,R-1)が生じるケースは、あまり多くないので先に列挙してしまおう。
その結果、Lに対しg(L,R)をRの昇順に並べると、値が変化する箇所は少ない。
よって、Aに対しLを総当たりしながら、g(L,R)が一致するRの区間に対し、最大値がその区間内になるケースを総当たりして数えて行けばよい。

int T,N,A[303030];
const ll mo=998244353;

vector<int> P[303030];
vector<int> cand[303030];
map<int,int> M[303030];
const int D=300000;
int S[303030];
ll p2[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,D) p2[i+1]=p2[i]*2%mo;
	
	for(i=2;i<=D;i++) {
		int cur=i;
		int m=1;
		vector<int> c;
		for(j=2;j*j<=cur;j++) if(cur%j==0) {
			m*=j;
			c.push_back(j);
			while(cur%j==0) cur/=j;
		}
		if(cur>1) {
			m*=cur;
			c.push_back(cur);
		}
		P[i]=c;
		cand[m].push_back(i);
		
		
	}
	for(i=1;i<=D;i++) {
		int mask;
		int sum=0;
		vector<int> V;
		FOR(mask,1<<P[i].size()) {
			int m=1;
			FOR(j,P[i].size()) if(mask&(1<<j)) m*=P[i][j];
			FORR(v,cand[m]) if(v>=i) V.push_back(v);
		}
		sort(ALL(V));
		M[i][i]=M[i][i+1]=i;
		int pre=i;
		FORR(a,V) if(a>i) {
			auto it=M[i-1].lower_bound(a);
			x=prev(it)->second;
			if(x!=pre) {
				M[i][a]=pre=x;
			}
		}
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>x;
			S[x]++;
		}
		
		FOR(i,N) S[i+1]+=S[i];
		
		ll ret=0;
		for(i=1;i<=N;i++) if(S[i]-S[i-1]) {
			x=S[i]-S[i-1];
			(ret+=i*(p2[x]-1))%=mo;
			int csum=0;
			for(auto it=M[i].lower_bound(i+1);it!=M[i].end();it++) {
				int nex=0;
				if(next(it)==M[i].end()) nex=N+1;
				else nex=min(N+1,next(it)->first);
				
				int num=S[nex-1]-S[it->first-1];
				int v=it->second;
				(ret+=v*(p2[x]-1)%mo*p2[csum]%mo*(p2[num]-1))%=mo;
				csum+=num;
				if(nex>N) break;
			}
		}
		cout<<ret<<endl;
		
		
		
		FOR(i,N+2) S[i]=0;
	}
}

まとめ

数列の要素を全部一致させるために、値を1ずつ動かすタイプの問題は、最小値と最大値だけ考えればいいってのを覚えておかないとな。