Codeforces #752 Div1 : C. Extreme Extension

1750ptの問題だけど、コードは短い。
https://codeforces.com/contest/1603/problem/C

問題

数列Bに対するextreme valueとは、以下を意味する。

• Bの要素を1つ選び、2つの(和が元の要素と等しい)正整数に分割して、元の要素の代わりに挿入する作業を考える。
• Bを昇順に保つのに必要な最小処理回数がextreme valueである

数列Aが与えられる。
Aの部分列におけるextreme valueの総和を求めよ。

解法

数列を逆順にみて降順にすることを考える。
f(n,v) := n要素目まで見たとき、末尾がvとなるようなAの部分列の個数
を管理し、nを小さい順に処理して行けばよい。
考えるべきvはA[n]の約数だけなので、それほどバリエーションはない。

int t,N,A[101010];
const ll mo=998244353;

pair<int,int> hoge(int nex,int cur) {
	if(cur<=nex) return {cur,0};
	int num=(cur+nex-1)/nex;
	return {cur/num,num-1};
	
}

unordered_map<int,ll> F;
unordered_map<int,ll> T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>t;
	while(t--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		ll ret=0;
		F.clear();
		FOR(i,N) {
			x=A[N-1-i];
			T.clear();
			T[x]=1;
			FORR2(a,b,F) {
				auto p=hoge(a,x);
				(ret+=b*p.second%mo*(N-i))%=mo;
				(T[p.first]+=b)%=mo;
			}
			swap(F,T);
		}
		cout<<ret<<endl;
	}
}

まとめ

逆順にすることに気付けば、後は割とすんなり、