每日 20260930 && 1002

No.1731 Product of Subsequence

K 很大，于是考虑按约数 DP，因为非约束不会提供贡献：
$$
f_{i+1,j} := f_{i+1,j} + f_{i, j}
$$

$$ f_{i+1, \gcd(K, j \times A_i)} := f_{i+1, \gcd(K, j \times A_i)} + f_{i,j} $$

就可以了，其中 $f_{i,j}$ 表示到第 i 个数字时候，选择的子序列的积的最大约数是 j 时候的子序列数目。

No.1095

namespace XK {

  void solve() {
  	INT N; cin >> N;
  	V<ll> A(N); rep(i, N) cin >> A[i];
  	set<ll> ls, rs;
  	rep(i, N) rs.insert(A[i]);
  	ls.insert(A[0]), rs.erase(A[0]);
  	ll ans = LINF;
  	rep(i, N - 1) {
  		rs.erase(A[i]);
  		ll ml = *ls.begin(), mr = *rs.begin();
  		if(ml < A[i] && mr < A[i]) chmin(ans, ml + mr + A[i]);
  		auto l = ls.upper_bound(A[i]), r = rs.upper_bound(A[i]);
  		if(l != ls.end() && r != rs.end()) {
  			chmin(ans, *l + *r + A[i]);
  		}
  		ls.insert(A[i]);
  	}
  	cout << (ans == LINF ? -1 : ans);
  }
};