結果
問題 | No.1972 Modulo Set |
ユーザー |
|
提出日時 | 2022-06-10 22:44:21 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 891 ms / 2,000 ms |
コード長 | 5,111 bytes |
コンパイル時間 | 4,145 ms |
コンパイル使用メモリ | 93,656 KB |
実行使用メモリ | 74,312 KB |
最終ジャッジ日時 | 2024-10-05 01:38:09 |
合計ジャッジ時間 | 25,132 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.HashMap; import java.util.NoSuchElementException; import java.util.Scanner; public class Main implements Runnable { public static void main(String[] args) throws IOException { new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); } long inv(long a) { return pow(a,p-2); } long ADD(long a,long b) { return a+b>=p?a+b-p:a+b; } long SUB(long a,long b) { return ADD(a,p-b); } long[] mul(long[] a, long[] b) { long[] c=new long[a.length+b.length-1]; for (int i=0;i<a.length;++i) { for (int j=0;j<b.length;++j) { c[i+j]+=a[i]*b[j]; c[i+j]%=p; } } return c; } long[] inv(long[] a) { int n=a.length; long[] G= {inv(a[0])}; for (int len=1;len<n;len*=2) { long[] prd=mul(mul(G,G),Arrays.copyOf(a, 2*len)); G=Arrays.copyOf(G, 2*len); for (int i=0;i<2*len;++i) { G[i]=(2*G[i]+p-prd[i])%p; } } return G; } long[] differentiate(long[] a) { long[] ret=new long[a.length]; for (int i=0;i+1<ret.length;++i) ret[i]=(i+1)*a[i+1]%p; return ret; } long[] integrate(long[] a) { long[] ret=new long[a.length]; for (int i=0;i+1<ret.length;++i) ret[i+1]=inv(i+1)*a[i]%p; return ret; } long[] log(long[] a) { return integrate(mul(differentiate(a),inv(a))); } long[] exp(long[] a) { int n=a.length; long[] G= {1}; for (int len=1;len<n;len*=2) { long[] log=log(Arrays.copyOf(G, 2*len)); for (int i=0;i<Math.min(n,2*len);++i) log[i]=(p-log[i]+a[i])%p; log[0]=ADD(log[0],1); G=Arrays.copyOf(mul(G,log),2*len); } return G; } class UnionFind { int[] parent; public UnionFind(int n) { parent=new int[n]; Arrays.fill(parent, -1); } int root(int x) { return parent[x]<0?x:(parent[x]=root(parent[x])); } boolean isroot(int x) { return parent[x]<0; } boolean equiv(int x, int y) { return root(x)==root(y); } void union(int x, int y) { x=root(x); y=root(y); if (x==y) return; parent[y]+=parent[x]; parent[x]=y; } int sz(int x) { return -parent[root(x)]; } } final long p=(long)1e9+7; long pow(long a, long n) { if (n==0) return 1; return pow(a*a%p,n/2)*(n%2==1?a:1)%p; } long gcd(long a, long b) { if (a==0) return b; return gcd(b%a, a); } int MAX=10000; long[] fac=new long[MAX]; long[] inv=new long[MAX]; long[] ifac=new long[MAX]; { Arrays.fill(fac, 1); Arrays.fill(ifac, 1); Arrays.fill(inv, 1); for (int i=2;i<MAX;++i) { fac[i]=fac[i-1]*i%p; inv[i]=p-(p/i)*inv[(int)(p%i)]%p; ifac[i]=inv[i]*ifac[i-1]%p; } } public void run() { Scanner sc = new Scanner(System.in); PrintWriter pw = new PrintWriter(System.out); int N=sc.nextInt(); long M=sc.nextLong(); long[] A=new long[N]; for (int i=0;i<N;++i) A[i]=sc.nextLong()%M; Arrays.sort(A); HashMap<Long, Integer> map=new HashMap<>(); for (long a : A) { map.merge(a, 1, Integer::sum); map.merge((M-a)%M, 0, Integer::sum); } long ans=0; for (var e : map.entrySet()) { long pair=(M-e.getKey())%M; if (pair != e.getKey()) { if (e.getValue() < map.get(pair) || (e.getValue()==map.get(pair) && e.getKey() < pair)) continue; } else if (pair == e.getKey()) { ans+=Math.min(1, e.getValue()); continue; } ans+=e.getValue(); } System.out.println(ans); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int) nextLong(); } }