Submission #74684454

---

Source Code Expand

#include <bits/stdc++.h>
namespace cjdst{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	template <typename T>
	class Sparse_Table{
		std::vector <std::vector <T>> st;
		int n;

		public:

		Sparse_Table(int n, std::vector <T> a){
			this -> n = n;
			st.resize(a.size() + 5, std::vector <T>(std::__lg(n) + 5));
			for(int i = 1; i <= n; i++){
				st[i][0] = a[i];
			}
			for(int i = 1; i <= std::__lg(n); i++){
				for(int j = 1; j <= n; j++){
					if(j + (1 << i) - 1 > n) break;
					st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
				}
			}
		}

		T query(int l, int r){
			int idx = std::__lg(r - l + 1);
			return std::max(st[l][idx], st[r - (1 << idx) + 1][idx]);
		}
	};

	template <typename T>
	class Fenwick_Tree{
		std::vector <T> tr;
		int n;

		public:

		Fenwick_Tree(){}
		Fenwick_Tree(int n, std::vector <T> a){
			tr.resize(n + 5, 0);
			this -> n = n;
			for(int i = 1; i <= n; i++){
				tr[i] += a[i];
				if(i + (i & (-i)) <= n){
					tr[i + (i & (-i))] += tr[i];
				}
			}
		}
		void modify(int idx, T val){
			for(int i = idx; i <= n; i += (i & (-i))) tr[i] += val;
		}
		T query(int idx){
			T ans = 0;
			for(int i = idx; i; i -= (i & (-i))) ans += tr[i];
			return ans;
		}
	};

	template <typename T>
	class Segtree{
		std::vector <T> tr;
		std::vector <int> left, right;
		std::vector <T> lazytag;
		void push_up(int u){
			tr[u] = tr[u << 1] + tr[u << 1 | 1];
		}
		void push_down(int u){
			tr[u << 1] += (right[u << 1] - left[u << 1] + 1) * lazytag[u];
			tr[u << 1 | 1] += (right[u << 1 | 1] - left[u << 1 | 1] + 1) * lazytag[u];
			lazytag[u << 1] += lazytag[u];
			lazytag[u << 1 | 1] += lazytag[u];
			lazytag[u] = 0;
		}
		void build(int u, int l, int r, std::vector <T> &a){
			left[u] = l, right[u] = r;
			if(l == r){
				tr[u] = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			build(u << 1, l, mid, a);
			build(u << 1 | 1, mid + 1, r, a);
			push_up(u);
		}
		void _modify(int u, int l, int r, T val){
			if(left[u] >= l && right[u] <= r){
				tr[u] += (right[u] - left[u] + 1) * val;
				lazytag[u] += val;
				return;
			}
			push_down(u);
			if(right[u << 1] >= l) _modify(u << 1, l, r, val);
			if(left[u << 1 | 1] <= r) _modify(u << 1 | 1, l, r, val);
			push_up(u);
		}
		T _query(int u, int l, int r){
			if(left[u] >= l && right[u] <= r){
				return tr[u];
			}
			push_down(u);
			T ans = 0;
			if(right[u << 1] >= l) ans += _query(u << 1, l, r);
			if(left[u << 1 | 1] <= r) ans += _query(u << 1 | 1, l, r);
			return ans;
		}

		public:

		Segtree(){}
		Segtree(int n, std::vector <T> a){
			tr.resize(n * 4 + 5);
			left.resize(n * 4 + 5);
			right.resize(n * 4 + 5);
			lazytag.resize(n * 4 + 5);
			build(1, 1, n, a);
		}
		void modify(int l, int r, T val){
			_modify(1, l, r, val);
		}
		T query(int l, int r){
			return _query(1, l, r);
		}
	};

	template <typename T>
	class Dynamic_Segtree{
		class node{
			public:

			T val;
			T lazytag;
			T left, right;
			node *lson, *rson;
			node(){
				val = lazytag = left = right = 0;
				lson = rson = 0;
			}
			node(T l, T r){
				val = (r + l) * (r - l + 1) / 2;
				lazytag = 0;
				lson = rson = 0;
				left = l, right = r;
			}
		}*root;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build_son(node *cur){
			if(cur -> lson) return;
			T l = cur -> left, r = cur -> right;
			T mid = (l + r) >> 1;
			cur -> lson = new node(l, mid);
			cur -> rson = new node(mid + 1, r);
		}

		void push_down(node *cur){
			T lazy = cur -> lazytag;
			node *ls = cur -> lson, *rs = cur -> rson;
			ls -> lazytag += lazy;
			rs -> lazytag += lazy;
			ls -> val += lazy * (ls -> right - ls -> left + 1);
			rs -> val += lazy * (rs -> right - rs -> left + 1);
			cur -> lazytag = 0;
		}

		void _modify(node *u, T l, T r, T val){
			if(u -> left >= l && u -> right <= r){
				u -> val += (u -> right - u -> left + 1) * val;
				u -> lazytag += val;
				return;
			}
			build_son(u);
			push_down(u);
			if(u -> lson -> right >= l) _modify(u -> lson, l, r, val);
			if(u -> rson -> left <= r) _modify(u -> rson, l, r, val);
			push_up(u);
		}

		T _query(node *u, T l, T r){
			if(u -> left >= l && u -> right <= r){
				return u -> val;
			}
			build_son(u);
			push_down(u);
			T ans = 0;
			if(u -> lson -> right >= l) ans += _query(u -> lson, l, r);
			if(u -> rson -> left <= r) ans += _query(u -> rson, l, r);
			return ans;
		}

		public:

		Dynamic_Segtree(){}
		Dynamic_Segtree(T l, T r){
			root = new node(l, r);
		}

		void modify(T l, T r, T val){
			_modify(root, l, r, val);
		}

		T query(T l, T r){
			return _query(root, l, r);
		}
	};

	template <typename T>
	class Mergable_Map{
		class node{
			public:

			T val;
			T left, right;
			node *lson, *rson;
			node(){
				val = left = right = 0;
				lson = rson = 0;
			}
			node(T l, T r){
				val = 0;
				lson = rson = 0;
				left = l, right = r;
			}
		}*root;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build_son(node *cur){
			if(cur -> lson) return;
			T l = cur -> left, r = cur -> right;
			T mid = (l + r) >> 1;
			cur -> lson = new node(l, mid);
			cur -> rson = new node(mid + 1, r);
		}

		void _modify(node *u, T idx, T val){
			if(u -> left == u -> right){
				u -> val += val;
				return;
			}
			build_son(u);
			if(u -> lson -> right >= idx) _modify(u -> lson, idx, val);
			else _modify(u -> rson, idx, val);
			push_up(u);
		}

		node *_merge(node *u, node *&v){
			if(!u) return v;
			if(!v) return u;
			if(u -> left == u -> right){
				u -> val += v -> val;
				return u;
			}
			u -> lson = _merge(u -> lson, v -> lson);
			u -> rson = _merge(u -> rson, v -> rson);
			if(u -> lson) push_up(u);
			return u;
		}

		T _get_val(node *u, T idx){
			if(!u) return 0;
			if(u -> left == u -> right) return u -> val;
			build_son(u);
			if(u -> lson -> right >= idx) return _get_val(u -> lson, idx);
			return _get_val(u -> rson, idx);
		}

		T _nth_element(node *u, T k){
			if(!u || u -> val < k) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			if(u -> lson -> val >= k) return _nth_element(u -> lson, k);
			return _nth_element(u -> rson, k - u -> lson -> val);
		}

		T _get_rank(node *u, T idx){
			if(!u) return 0;
			if(u -> left == u -> right) return u -> val;
			build_son(u);
			if(u -> lson -> right >= idx) return _get_rank(u -> lson, idx);
			return _get_rank(u -> rson, idx) + u -> lson -> val;
		}

		T _get_pre(node *u, T idx){
			if(!u || !u -> val) return 0;
			if(u -> left >= idx) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			T ans = _get_pre(u -> rson, idx);
			if(ans) return ans;
			return _get_pre(u -> lson, idx);
		}

		T _get_next(node *u, T idx){
			if(!u || !u -> val) return 0;
			if(u -> right <= idx) return 0;
			if(u -> left == u -> right) return u -> left;
			build_son(u);
			T ans = _get_next(u -> lson, idx);
			if(ans) return ans;
			return _get_next(u -> rson, idx);
		}


		public:

		Mergable_Map(){}
		Mergable_Map(T l, T r){
			root = new node(l, r);
		}

		void modify(T idx, T val){
			_modify(root, idx, val);
		}

		T query(){
			return _query(root);
		}

		void merge(Mergable_Map &v){
			_merge(root, v.root);
			v = Mergable_Map(root -> left, root -> right);
		}

		T get_val(T idx){
			return _get_val(root, idx);
		}

		T nth_element(T k){
			return _nth_element(root, k);
		}

		T get_rank(T idx){
			return _get_rank(root, idx - 1) + 1;
		}

		T get_pre(T idx){
			return _get_pre(root, idx);
		}

		T get_next(T idx){
			return _get_next(root, idx);
		}
	};

    template <typename T>
	class HJT_Segtree{
		class node{
			public:

			T val;
			int left, right;
			node *lson, *rson;
			node(){
				val = left = right = 0;
				lson = rson = 0;
			}
		};
		std::vector <node*> roots;
		int len;

		void push_up(node *cur){
			cur -> val = cur -> lson -> val + cur -> rson -> val;
		}

		void build(node *cur, int l, int r, std::vector <T> &a){
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = a[l];
				return;
			}
			int mid = (l + r) >> 1;
			node *ls = new node, *rs = new node;
			cur -> lson = ls;
			cur -> rson = rs;
			build(ls, l, mid, a);
			build(rs, mid + 1, r, a);
			push_up(cur);
		}

		void _build_new(node *cur, node *pre, int idx, T val){
			int l = pre -> left;
			int r = pre -> right;
			cur -> left = l;
			cur -> right = r;
			if(l == r){
				cur -> val = val;
				return;
			}
			int mid = (l + r) >> 1;
			node *ls, *rs;
			if(idx <= mid){
				ls = new node, rs = pre -> rson;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(ls, pre -> lson, idx, val);
			}else{
				ls = pre -> lson, rs = new node;
				cur -> lson = ls, cur -> rson = rs;
				_build_new(rs, pre -> rson, idx, val);
			}
			push_up(cur);
		}

		T _query(node *cur, int l, int r){
			if(cur -> left >= l && cur -> right <= r){
				return cur -> val;
			}
			T ans = 0;
			if(cur -> lson -> right >= l) ans += _query(cur -> lson, l, r);
			if(cur -> rson -> left <= r) ans += _query(cur -> rson, l, r);
			return ans;
		}

		public:

		HJT_Segtree(){len = 0;}
		HJT_Segtree(int n, std::vector <T> a){
			node *root = new node;
			build(root, 1, n, a);
			roots.push_back(root);
		}

		void build_new(int pre, int idx, T val){
			node *cur = new node;
			_build_new(cur, roots[pre], idx, val);
			roots.push_back(cur);
		}

		T query(int pre, int l, int r){
			roots.push_back(roots[pre]);
			return _query(roots[pre], l, r);
		}
	};

	template <typename T>
	class Block{
		std::vector <T> a;
		std::vector <T> b;
		std::vector <T> lazytag;
		std::vector <int> belong, left, right;
		int n, len;

		void push_down(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				a[i] += lazytag[idx];
			}
			lazytag[idx] = 0;
		}

		void push_up(int idx){
			for(int i = left[idx]; i <= right[idx]; i++){
				b[i] = a[i];
			}
			std::sort(b.begin() + left[idx], b.begin() + right[idx] + 1);
		}

		public:

		Block(){}
		Block(int n, std::vector <T> a){
			this -> n = n;
			len = sqrtl(n) + 1;
			this -> a.resize(n + 5);
			b.resize(n + 5);
			lazytag.resize(n / len + 5);
			belong.resize(n + 5);
			left.resize(n / len + 5);
			right.resize(n / len + 5);

			for(int i = 1; i <= n; i++){
				this -> a[i] = a[i];
				b[i] = a[i];
				belong[i] = (i - 1) / len + 1;
				right[belong[i]] = i;
				if(!left[belong[i]]) left[belong[i]] = i;
			}
			for(int i = 1; left[i]; i++){
				std::sort(b.begin() + left[i], b.begin() + right[i] + 1);
			}
		}

		void modify(int l, int r, T val){
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				for(int i = l; i <= r; i++){
					a[i] += val;
				}
				push_up(belong[l]);
				return;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			for(int i = l; i <= right[curl]; i++){
				a[i] += val;
			}
			for(int i = curl + 1; i < curr; i++){
				lazytag[i] += val;
			}
			for(int i = left[curr]; i <= r; i++){
				a[i] += val;
			}
			push_up(curl), push_up(curr);
		}

		T query(int l, int r, T val){
			T ans = 0;
			if(belong[l] == belong[r]){
				push_down(belong[l]);
				push_up(belong[l]);
				for(int i = l; i <= r; i++){
					if(a[i] < val) ans = std::max(ans, a[i]);
				}
				return ans;
			}
			int curl = belong[l], curr = belong[r];
			push_down(curl), push_down(curr);
			push_up(curl), push_up(curr);
			for(int i = l; i <= right[curl]; i++){
				if(a[i] < val) ans = std::max(ans, a[i]);
			}
			for(int i = curl + 1; i < curr; i++){
				int idx = lower_bound(b.begin() + left[i], b.begin() + right[i] + 1, val - lazytag[i]) - b.begin() - 1;
				if(idx >= left[i]) ans = std::max(ans, b[idx] + lazytag[i]);
			}
			for(int i = left[curr]; i <= r; i++){
				if(a[i] < val) ans = std::max(ans, a[i]);
			}
			return ans;
		}
	};
	
	template <typename T>
	class FHQ_Treap{
		class node{
			public:

			T key, val, siz;
			ull pri;
			node *lson, *rson;
			node(T _k, T _v, ull _p){
				key = _k, val = _v, pri = _p;
				siz = _v;
				lson = rson = 0;
			}
		}*root;
		std::mt19937_64 rng;

		void push_up(node *cur){
			cur -> siz = cur -> val;
			if(cur -> lson) cur -> siz += cur -> lson -> siz;
			if(cur -> rson) cur -> siz += cur -> rson -> siz;
		}

		node *merge(node *x, node *y){
			if(!x && !y) return 0;
			if(!x) return y;
			if(!y) return x;
			if(x -> pri > y -> pri){
				y -> lson = merge(x, y -> lson);
				push_up(y);
				return y;
			}else{
				x -> rson = merge(x -> rson, y);
				push_up(x);
				return x;
			}
		}

		void split(node *cur, T x, node *&l, node *&r){
			if(!cur){
				l = 0, r = 0;
				return;
			}
			if(cur -> key > x){
				r = cur;
				split(cur -> lson, x, l, cur -> lson);
			}else{
				l = cur;
				split(cur -> rson, x, cur -> rson, r);
			}
			push_up(cur);
		}

		public:

		FHQ_Treap(){}
		FHQ_Treap(ull s){
			root = 0;
			rng.seed(s);
		}

		void modify(T key, T val){
			node *l, *mid, *r;
			split(root, key, l, r);
			split(l, key - 1, l, mid);

			if(!mid) mid = new node(key, val, rng());
			else{
				mid -> val += val;
				push_up(mid);
				if(!mid -> val){
					root = merge(l, r);
					return;
				}
			}
			root = merge(merge(l, mid), r);
		}

		T get_rank(T val){
			node *l, *r;
			split(root, val - 1, l, r);
			ll ans = (l ? l -> siz : 0);
			root = merge(l, r);
			return ans + 1;
		}

		T _nth_element(node *cur, T k){
			int lsize = 0;
			if(cur -> lson) lsize = cur -> lson -> siz;
			if(k <= lsize) return _nth_element(cur -> lson, k);
			if(k <= lsize + cur -> val) return cur -> key;
			return _nth_element(cur -> rson, k - lsize - cur -> val);
		}
		T nth_element(T k){
			return _nth_element(root, k);
		}

		T get_pre(T val){
			node *l, *r;
			split(root, val - 1, l, r);
			node *cur = l;
			ll ans = 0;
			while(cur){
				ans = cur -> key;
				cur = cur -> rson;
			}
			root = merge(l, r);
			return ans;
		}

		T get_next(T val){
			node *l, *r;
			split(root, val, l, r);
			node *cur = r;
			ll ans = 0;
			while(cur){
				ans = cur -> key;
				cur = cur -> lson;
			}
			root = merge(l, r);
			return ans;
		}
	};
	
	class Tree_Spliter{
		std::vector <std::vector <int>> edges;
		std::vector <int> dfn, dep, father, head, rank, son, siz;


		void dfs(int cur, int fa){
			father[cur] = fa;
			siz[cur] = 1;
			dep[cur] = dep[fa] + 1;
			for(int i:edges[cur]){
				if(i == fa) continue;
				dfs(i, cur);
				siz[cur] += siz[i];
				if(siz[son[cur]] < siz[i]) son[cur] = i;
			}
		}
		void dfs2(int cur, int top, int &curdfn){
			head[cur] = top;
			curdfn++;
			dfn[cur] = curdfn;
			rank[curdfn] = cur;
			if(!son[cur]) return;
			dfs2(son[cur], top, curdfn);
			for(int i:edges[cur]){
				if(i != son[cur] && i != father[cur]) dfs2(i, i, curdfn);
			}
		}

		public:

		Tree_Spliter(){}
		Tree_Spliter(int n, int root, std::vector <std::vector <int>> a){
			dfn.resize(n + 5), dep.resize(n + 5), father.resize(n + 5);
			head.resize(n + 5), rank.resize(n + 5);
			son.resize(n + 5), siz.resize(n + 5);

			edges = a;
			dfs(root, 0);
			int curdfn = 0;
			dfs2(root, root, curdfn);
		}

		int get_lca(int x, int y){
			int hx = head[x], hy = head[y];
			while(hx != hy){
				if(dep[hx] < dep[hy]) y = father[hy], hy = head[y];
				else x = father[hx], hx = head[x];
			}
			return (dep[x] < dep[y] ? x : y);
		}

		std::vector <pii> get_path(int x, int y){
			std::vector <pii> ans;
			int hx = head[x], hy = head[y];
			while(hx != hy){
				if(dep[hx] < dep[hy]){
					ans.push_back({dfn[hy], dfn[y]});
					y = father[hy], hy = head[y];
				}
				else{
					ans.push_back({dfn[hx], dfn[x]});
					x = father[hx], hx = head[x];
				}
			}
			if(dfn[x] > dfn[y]) std::swap(x, y);
			ans.push_back({dfn[x], dfn[y]});
			return ans;
		}

		pii get_subtree(int idx){
			return {dfn[idx], dfn[idx] + siz[idx] - 1};
		}

		int node_to_dfn(int idx){
			return dfn[idx];
		}
		int dfn_to_node(int idx){
			return rank[idx];
		}
	};
	
	class Trie{
		class node{
			public:

			node *next[26];
			int val;
			node(){
				memset(next, 0, sizeof(next));
				val = 0;
			}
		}*root;

		public:

		Trie(){
			root = new node;
		}

		void insert(std::string &s){
			node *cur = root;
			cur -> val++;
			for(char c:s){
				if(!cur -> next[c - 'a']) cur -> next[c - 'a'] = new node;
				cur = cur -> next[c - 'a'];
				cur -> val++;
			}
		}

		int find_pre(std::string &s){
			node *cur = root;
			for(char c:s){
				if(!cur -> next[c - 'a']) return 0;
				cur = cur -> next[c - 'a'];
			}
			return cur -> val;
		}
	};

	class dsu{
		std::vector <int> father, siz;

		public:

		int n, unions;
		dsu(){
			n = 0;
		}
		dsu(int n){
			this -> n = n;
			unions = n;
			father.resize(n + 5, 0);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] < siz[y]) std::swap(x, y);
			siz[x] += siz[y];
			father[y] = x;
			unions--;
		}
	};

	template <typename T, int siz>
	class matrix{
		public:

		std::vector <std::vector <T>> a;
		T mod;
		matrix(T m){
			a.resize(siz, std::vector <T>(siz, 0));
			mod = m;
		}
		matrix(std::vector <std::vector <T>> v, T m){
			a = v;
			mod = m;
		}
		matrix operator * (matrix <T, siz> b){
			matrix <T, siz> ans(mod);
			for(int i = 0; i < siz; i++){
				for(int k = 0; k < siz; k++){
					for(int j = 0; j < siz; j++){
						ans.a[i][j] += a[i][k] * b.a[k][j] % mod;
						ans.a[i][j] %= mod;
					}
				}
			}
			return ans;
		}
	};

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}
	
	// 卡常吗这 
	const int N = 1000000, mod = 998244353;
	
	ll a[N + 5], b[N + 5], pre[N + 5], pre2[N + 5], n, m, ans;

	void solve(){
		std::cin >> n >> m;
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			pre[i] = (pre[i - 1] + a[i]) % mod;
			pre2[i] = (pre2[i - 1] + a[i] * i) % mod;
		}
		for(int i = n + 1; i <= n + m; i++){
			pre[i] = pre[i - 1];
			pre2[i] = pre2[i - 1];
		}
		for(int i = 1; i <= m; i++){
			std::cin >> b[i];
		}
		for(int i = 1; i <= m; i++){
			for(int j = i; j <= n + m; j += i){
				// ll p = ans;
				ans += (pre2[j - 1] - pre2[j - i] + mod) % mod * b[i] % mod;
				ans -= ((pre[j - 1] - pre[j - i] + mod) % mod) % mod * b[i] % mod * (j - i) % mod;
				ans = (ans % mod + mod) % mod;
				// std::cout << "[" << j - i + 1 << ", " << j << "] " << i << ": " << ans - p << '\n';
			}
			// std::cout << ans << '\n';
		}
		std::cout << ans << '\n';
	}
}


int main(){
	cjdst::init();
	int T = 1;
	// std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}

Submission Info

Judge Result