Div2 D. Effects of Anti Pimples
解题思路
- 将由小到大排序
- 若不考虑绿色的情况则为最大值的情况为,即选择在它之前的点
- 对于同时选,会被统计贡献时考虑
- 考虑绿色,对于每个,若选则均选
- 对于每个预处理出,记作
- 对由小到大排序
- 为答案的情况为
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Vector;
//implements Runnable
public class Main {
static long md=(long)998244353;
static long Linf=Long.MAX_VALUE/2;
static int inf=Integer.MAX_VALUE/2;
static int N=100010;
static int n=0;
static int m=0;
static
class Node{
long x;
long y;
public Node() {
}
public Node(long u,long v) {
x=u;
y=v;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node now = (Node) o;
return x==now.x&&y==now.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
static void solve() throws Exception{
AReader input=new AReader();
// Scanner input=new Scanner(System.in);
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
String al="abcdefghijklmnopqrstuvwxyz";
char[] ac=al.toCharArray();
boolean[] isnotpri=new boolean[N+1];
// int T=input.nextInt();
// while(T>0) {
// T--;
// }
n=input.nextInt();
int[] a=new int[n+1];
HashMap<Integer, Integer> hs=new HashMap<Integer, Integer>();
int sum=n;
for(int i=1;i<=n;++i) {
a[i]=input.nextInt();
if(hs.get(a[i])==null) {
hs.put(a[i], 1);
}else {
int z=hs.get(a[i]);
hs.put(a[i], z+1);
}
}
int[] mx=new int[n+1];
for(int i=1;i<=n;++i) {
mx[i]=a[i];
for(int j=i*2;j<=n;j+=i) {
mx[i]=Math.max(mx[i], a[j]);
}
}
Arrays.sort(mx,1,n+1);
long ans=0;
long now=1;
for(int i=1;i<=n;++i) {
ans=(ans+now*mx[i]%md)%md;
now=now*2%md;
}
out.println(ans);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
solve();
}
// public static final void main(String[] args) throws Exception {
// new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
// }
// @Override
// public void run() {
// try {
// //原本main函数的内容
// solve();
//
// } catch (Exception e) {
// }
// }
static
class AReader{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public AReader(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
//确定下一个token只有一个字符的时候再用
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println() throws IOException {
bw.newLine();
}
public void println(int[] arr) throws IOException{
for (int value : arr) {
bw.write(value + " ");
}
println();
}
public void println(int l, int r, int[] arr) throws IOException{
for (int i = l; i <= r; i ++) {
bw.write(arr[i] + " ");
}
println();
}
public void println(int a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(int a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(String a) throws IOException{
bw.write(a);
bw.newLine();
}
public void print(String a) throws IOException{
bw.write(a);
}
public void println(long a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(long a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(double a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(double a) throws IOException{
bw.write(String.valueOf(a));
}
public void print(char a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(char a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
}
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/491521.html
如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!