なるほど…。
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ずつ動かすタイプの問題は、最小値と最大値だけ考えればいいってのを覚えておかないとな。