提出 #72041479

---

ソースコード 拡げる

/**
	author:  shobonvip
	created: 2025.12.27 21:36:56
**/

#include<bits/stdc++.h>
using namespace std;

//* ATCODER
#include<atcoder/all>
using namespace atcoder;
typedef modint998244353 mint;
//*/

/* BOOST MULTIPRECISION
#include<boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
//*/

typedef long long ll;

#define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--)
#define all(v) v.begin(), v.end()

template <typename T> bool chmin(T &a, const T &b) {
	if (a <= b) return false;
	a = b;
	return true;
}

template <typename T> bool chmax(T &a, const T &b) {
	if (a >= b) return false;
	a = b;
	return true;
}

template <typename T> T max(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmax(ret, a[i]);
	return ret;
}

template <typename T> T min(vector<T> &a){
	assert(!a.empty());
	T ret = a[0];
	for (int i=0; i<(int)a.size(); i++) chmin(ret, a[i]);
	return ret;
}

template <typename T> T sum(vector<T> &a){
	T ret = 0;
	for (int i=0; i<(int)a.size(); i++) ret += a[i];
	return ret;
}

mint solve(ll n, ll m, ll k, vector<int> a, vector<int> b) {

	if (n > m) {
		swap(n, m);
		swap(a, b);
	}

	ll gcd = __gcd(n, m);

	if (gcd > 1) {
		vector ag(gcd, vector<int>(n / gcd));
		vector bg(gcd, vector<int>(m / gcd));
		rep(i,0,n) ag[i % gcd][i / gcd] = a[i];
		rep(i,0,m) bg[i % gcd][i / gcd] = b[i];
		mint ans = 0;
		rep(i,0,gcd) {
			ll times = (k - i + gcd - 1) / gcd;
			ans += solve(n/gcd, m/gcd, times, ag[i], bg[i]);
		}
		return ans;
	}

	vector<int> p;
	vector<bool> seen(m);
	rep(i,0,m) {
		if (seen[i]) continue;
		int x = i;
		while (!seen[x]) {
			seen[x] = 1;
			p.emplace_back(x);
			x += n;
			x %= m;
		}
	}

	vector<int> q(m);
	rep(i,0,m) q[p[i]] = i;

	int sz = 1;
	while (sz < 2*m) sz *= 2;
	vector<mint> fw1(2*sz);

	ll lcm = n * m;
	ll kuri = k / lcm;
	ll amari = k % lcm;
	vector<pair<ll,ll>> piv;
	rep(i,0,n) piv.emplace_back(pair(a[i], 0));
	rep(i,0,m) piv.emplace_back(pair(b[i], 1));
	sort(all(piv));
	reverse(all(piv));
	mint kurisum = 0;
	mint anum = 0;
	mint bnum = 0;

	rep(i,0,n+m) {
		if (piv[i].second == 0) {
			kurisum += bnum * piv[i].first;
			anum++;
		}
		if (piv[i].second == 1) {
			kurisum += anum * piv[i].first;
			bnum++;
		}
	}

	mint ans = kurisum * kuri;
	vector que(2*sz, vector<pair<ll,int>>(0));
	rep(i,0,2*m) {
		int x = i + sz;
		while (x > 0) {
			que[x].emplace_back(b[p[i%m]], 1);
			fw1[x] += b[p[i%m]];
			x >>= 1;
		}
	}

	rep(i,0,n) {
		int f = i % m;
		ll var = (amari - i + n - 1) / n;
		ll l = q[f];
		ll r = q[f] + var;

		//cout << l << ' ' << r << endl;
		l += sz, r += sz;
		while (l < r) {
			if (l & 1) {
				que[l].emplace_back(a[i], 0);
				l++;
			}
			if (r & 1) {
				r--;
				que[r].emplace_back(a[i], 0);
			}
			l >>= 1;
			r >>= 1;
		}
	}

	rep(i,0,2*sz) {
		sort(all(que[i]));
		reverse(all(que[i]));
	}

	rep(i,0,2*sz) {
		mint now_nums = 0;
		mint now_sums = fw1[i];
		for (auto [x,t]: que[i])  {
			if (t == 1) {	
				now_sums -= x;
				now_nums += 1;
			} else {
				ans += now_sums + now_nums * x;
			}
		}
	}

	return ans;

}

mint naive(ll n, ll m, ll k, vector<int> a, vector<int> b) {
	mint ans=0;
	rep(i,0,k) {
		ans+=min(a[i%n],b[i%m]);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(m);
	rep(i,0,n) {
		cin >> a[i];
	}
	rep(i,0,m) {
		cin >> b[i];
	}
	
	mint ans = solve(n, m, k, a, b);
	cout << ans.val() << endl;
	//cout << naive(n,m,k,a,b).val()<<endl;
	
}

提出情報

ジャッジ結果