結果
| 問題 | No.1189 Sum is XOR |
| ユーザー |
 CaliPota
|
| 提出日時 | 2020-08-22 16:47:01 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 919 ms / 2,000 ms |
| コード長 | 19,296 bytes |
| コンパイル時間 | 4,285 ms |
| コンパイル使用メモリ | 91,220 KB |
| 実行使用メモリ | 40,160 KB |
| 最終ジャッジ日時 | 2024-10-15 10:49:13 |
| 合計ジャッジ時間 | 13,037 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 497 ms
39,564 KB |
| testcase_01 | AC | 236 ms
40,160 KB |
| testcase_02 | AC | 164 ms
39,580 KB |
| testcase_03 | AC | 96 ms
38,564 KB |
| testcase_04 | AC | 95 ms
38,308 KB |
| testcase_05 | AC | 102 ms
38,640 KB |
| testcase_06 | AC | 105 ms
38,860 KB |
| testcase_07 | AC | 92 ms
38,576 KB |
| testcase_08 | AC | 83 ms
37,956 KB |
| testcase_09 | AC | 85 ms
38,204 KB |
| testcase_10 | AC | 82 ms
37,320 KB |
| testcase_11 | AC | 501 ms
38,724 KB |
| testcase_12 | AC | 171 ms
39,508 KB |
| testcase_13 | AC | 516 ms
39,920 KB |
| testcase_14 | AC | 495 ms
38,816 KB |
| testcase_15 | AC | 919 ms
38,996 KB |
| testcase_16 | AC | 558 ms
38,664 KB |
| testcase_17 | AC | 792 ms
38,772 KB |
| testcase_18 | AC | 190 ms
38,844 KB |
| testcase_19 | AC | 502 ms
39,044 KB |
| testcase_20 | AC | 633 ms
39,004 KB |
| testcase_21 | AC | 60 ms
37,280 KB |
| testcase_22 | AC | 65 ms
36,960 KB |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.NoSuchElementException;
public class Main {
//私が好きなアルゴリズム : 累積和・UF木
//PriorityQueueは拡張for文で出すとsortされてない順番で出てくるよ
//longのbit演算は1L<<posに注意
//long long
//JOIはMLEが厳しい。shortというものがあるよ。あと、ArrayListはオートボクシングが遅いから、自作listが早いよ
public static void main(String[] args) throws Exception {
FastScanner sc = new FastScanner();
PrintWriter out = new PrintWriter(System.out);
int n = sc.nexI();
int k = sc.nexI();
int[] dt = new int[1024];
fill(dt, 0);
for(int i=0; i<n; i++) {
int dw = sc.nexI();
dt[dw]++;
}
if(k>10) {
System.out.println(0);
return;
}
long ans = saiki(dt, 0, k, 0);
out.println(ans);
out.flush();
return;
}
private static long saiki(int[] dt, int already, int rest, int predubble) {
if(rest==0) return 1;
if(already==1023) return 0;
long ans = 0L;
for(int i=predubble; i<1024; i++) {
if((i&already) == 0) { //許容
ans += dt[i]*saiki(dt, already|i, rest-1, i+1);
ans %= e99;
}
}
return ans;
}
private static int INF = 100000000;
private static long INFL = 100000000000000000L;
private static long e97 = 1000000007L;
private static long e99 = 998244353L;
private static void assertion(boolean b) {
if(!b) throw new AssertionError();
}
private static int pow2(int in) {
return in*in;
}
private static long pow2(long in) {
return in*in;
}
private static double pow2(double in) {
return in*in;
}
private static int getDigit2(long num) {
long cf = 1;
int d = 0;
while(num > cf) {
d ++;
cf = (1L<<d);
}
return d; //numは2^d以下
}
private static int getDigit10(long num) {
long cf = 1L;
int d = 0;
while(num >= cf) {
d ++;
cf *= 10L;
}
return d; //numはd桁の数で、10^dより小さい
}
private static int divceil(int nume, int deno) {
return (nume+deno-1)/deno;
}
private static long divceil(long nume, long deno) {
return (nume+deno-1L)/deno;
}
private static boolean isINF(long in) {
if((in*20L)>INF) return true;
else return false;
}
private static boolean isINFL(long in) {
if((in*10L)>INFL) return true;
else return false;
}
public static int biSearchMax(long[] dt, long target) {
int left=-1, right=dt.length, mid=-1;
while((right-left)>1) {
mid = (right+left)/2;
if(dt[mid] < target) left=mid;
else right=mid;
}
return left; //target未満の最大のaddress
}
public static int biSearchmin(long[] dt, long target) { //単調減少文字列
int left=-1, right=dt.length, mid=-1;
while((right-left)>1) {
mid = (right+left)/2;
if(dt[mid] > target) left=mid;
else right=mid;
}
return left; //targetより大きい最大のaddress
}
public static int biSearchMaxAL(ArrayList<Long> dt, long target) {
int left=-1, right=dt.size(), mid=-1;
while((right-left)>1) {
mid = (right+left)/2;
if(dt.get(mid) <= target) left=mid;
else right=mid;
}
return left;//target以下の最大のaddress
}
private static int[] Xdir4 = {1,0,0,-1};
private static int[] Ydir4 = {0,1,-1,0};
private static int[] Xdir8 = {1,1,1,0,0,-1,-1,-1};
private static int[] Ydir8 = {1,0,-1,1,-1,1,0,-1};
private static boolean is_in_area(int y, int x, int h, int w) {
if(y < 0) return false;
if(x < 0) return false;
if(y >= h) return false;
if(x >= w) return false;
return true;
}
private static int abs(int a) {
return (a>=0) ? a: -a;
}
private static long abs(long a) {
return (a>=0) ? a: -a;
}
private static double abs(double a) {
return (a>=0) ? a: -a;
}
private static int min(int a, int b) {
return (a>b) ? b : a;
}
private static long min(long a, long b) {
return (a>b) ? b : a;
}
private static double min(double a, double b) {
return (a>b) ? b : a;
}
private static int max(int a, int b) {
return (a>b) ? a : b;
}
private static long max(long a, long b) {
return (a>b) ? a : b;
}
private static double max(double a, double b) {
return (a>b) ? a : b;
}
private static int minN(int... ins) {
int min = ins[0];
for(int i=1; i<ins.length; i++) {
if(ins[i] < min) min = ins[i];
}
return min;
}
private static long minN(long... ins) {
long min = ins[0];
for(int i=1; i<ins.length; i++) {
if(ins[i] < min) min = ins[i];
}
return min;
}
private static int maxN(int... ins) {
int max = ins[0];
for(int i=1; i<ins.length; i++) {
if(ins[i] > max) max = ins[i];
}
return max;
}
private static long maxN(long... ins) {
long max = ins[0];
for(int i=1; i<ins.length; i++) {
if(ins[i] > max) max = ins[i];
}
return max;
}
private static int minExAd(int[] dt, int ad) {
int min = Integer.MAX_VALUE;
for(int i=0; i<dt.length; i++) {
if((i!=ad) && (dt[i]<min)) min = dt[i];
}
return min;
}
private static long minExAd(long[] dt, int ad) {
long min = Long.MAX_VALUE;
for(int i=0; i<dt.length; i++) {
if((i!=ad) && (dt[i]<min)) min = dt[i];
}
return min;
}
private static int minExVal(int[] dt, int ex_val) {
int min = Integer.MAX_VALUE;
for(int i=0; i<dt.length; i++) {
if((dt[i]!=ex_val) && (dt[i]<min)) min = dt[i];
}
return min;
}
private static long minExVal(long[] dt, long ex_val) {
long min = Long.MAX_VALUE;
for(int i=0; i<dt.length; i++) {
if((dt[i]!=ex_val) && (dt[i]<min)) min = dt[i];
}
return min;
}
private static int maxExAd(int[] dt, int ad) {
int max = Integer.MIN_VALUE;
for(int i=0; i<dt.length; i++) {
if((i!=ad) && (dt[i]>max)) max = dt[i];
}
return max;
}
private static long maxExAd(long[] dt, int ad) {
long max = Long.MIN_VALUE;
for(int i=0; i<dt.length; i++) {
if((i!=ad) && (dt[i]>max)) max = dt[i];
}
return max;
}
private static int maxExVal(int[] dt, int ex_val) {
int max = Integer.MIN_VALUE;
for(int i=0; i<dt.length; i++) {
if((dt[i]!=ex_val) && (dt[i]>max)) max = dt[i];
}
return max;
}
private static long maxExVal(long[] dt, long ex_val) {
long max = Long.MIN_VALUE;
for(int i=0; i<dt.length; i++) {
if((dt[i]!=ex_val) && (dt[i]>max)) max = dt[i];
}
return max;
}
private static int sumA(int[] dt) {
int sum = 0;
for(int e: dt) {
sum += e;
}
return sum;
}
private static long sumA(long[] dt) {
long sum = 0L;
for(long e: dt) {
sum += e;
}
return sum;
}
private static long sumA(ArrayList<Long> dt) {
long sum =0L;
for(long e: dt) {
sum += e;
}
return sum;
}
private static int pow(int n, int k) {
int ans = 1;
for(int i=0; i<k; i++) {
ans *= n;
assertion(n>=0);
}
return ans;
}
private static long pow(long n, int k) {
long ans = 1L;
for(int i=0; i<k; i++) {
ans *= n;
assertion(n>=0L);
}
return ans;
}
private static double hypod(double a, double b) {
return Math.sqrt(a*a+b*b);
}
private static long factorial(int n) {
long ans=1L;
for(long i=n; i>0; i--) {
ans *= i;
assertion(ans>=0L);
}
return ans;
}
private static long facP(int n, long p) {
long ans=1L;
for(long i=n; i>0; i--) {
ans *= i;
ans %= p;
}
return ans;
}
private static long lcm(long m, long n) {
assertion((m>0L) && (n>0L));
long ans = m/gcd(m,n);
ans *= n;
return ans;
}
private static long gcd(long m, long n) {
if(isINFL(-m)) return n;
assertion((m>=0L) && (n>=0L));
if(m < n) return gcd(n, m);
if(n == 0) return m;
return gcd(n, m % n);
}
private static boolean is_prime(long a) {
if(a==1) return false;
for(long i=2L; i<=Math.sqrt(a); i++) {
if(a%i == 0) return false;
}
return true;
}
private static long modinv(long a, long p) {
assertion((a>0)&&(p>1)&&(a%p != 0));
//a|p, >1に注意
long b = p, u = 1L, v = 0L;
while (b > 0) {
long t = a / b;
long pe = a%b;
a = b;
b = pe;
pe = u-t*v;
u = v;
v = pe;
}
u %= p;
if(u < 0L) u += p;
return u;
}
private static long pow10E97(long ob, long soeji, long p) { //繰り返し二乗法
if(ob==0) return 0L;
if(soeji==0) return 1L;
if(soeji==2) return (ob*ob)%p;
long cf = 1L;
int d = 0;
while(soeji >= cf) {
d ++;
cf = (1L<<d);
}
long[] ob_pow_2pow = new long[d];
ob_pow_2pow[0] = ob;
for(int i=1; i<d; i++) {
ob_pow_2pow[i] = (ob_pow_2pow[i-1]*ob_pow_2pow[i-1])%p;
}
long ans=1L;
for(long i=(d-1); i>=0L; i--) {
if(soeji >= (1L<<i)) {
soeji -= (1L<<i);
ans = (ans*ob_pow_2pow[(int)i])%p;
}
}
return ans%p;
}
private static int inC2(int n) {
return ((n*(n-1))/2);
}
private static long nC2(long n) {
return ((n*(n-1L))/2L);
}
private static int intflag(int pos) {
assertion(pos<31);
return (1<<pos);
}
private static long flag(long pos) {
assertion(pos<63);
return (1L<<pos);
}
private static boolean isFlaged(int bit, int pos) {
if((bit&(1<<pos)) > 0) return true;
else return false;
}
private static boolean isFlaged(long bit, int pos) {
if((bit&(1L<<pos)) > 0L) return true;
else return false;
}
private static int ideflag(int bit, int pos) {
return bit&~(1<<pos);
}
private static int countFlaged(int bit) {
int ans=0;
for(int i=0; i<31; i++) {
if((bit&(1<<i)) > 0) ans++;
}
return ans;
}
private static int countFlaged(long bit) {
int ans=0;
for(long i=0; i<63; i++) {
if((bit&(1L<<i)) > 0) ans++;
}
return ans;
}
public static int biSearch(int[] dt, int target) {
int left=0, right=dt.length-1;
int mid=-1;
while(left<=right) {
mid = (right+left)/2;
if(dt[mid] == target) return mid;
if(dt[mid] < target) left=mid+1;
else right=mid-1;
}
return -1;
}
private static void show2(int bit) {
for(int i=0; i<getDigit2(bit); i++) {
if(isFlaged(bit,i)) System.out.print("O");
else System.out.print(".");
}
System.out.println();
}
static void show2(boolean[][] dt, int lit_x, int lit_y) {
for(int j=0; j<dt.length; j++) {
for(int i=0; i<dt[j].length; i++) {
if((i==lit_y) && (j==lit_x)) System.out.print("X");
else if(dt[j][i]) System.out.print("O");
else System.out.print(".");
}
System.out.println();
}
}
static void show2(int[][] dt, String cmnt) {
for(int i=0; i<dt.length; i++) {
for(int j=0; j<dt[i].length; j++) {
System.out.print(dt[i][j]+",");
}
System.out.println("<-"+cmnt+":"+i);
}
}
static void show2(long[][] dt, String cmnt) {
for(int i=0; i<dt.length; i++) {
for(int j=0; j<dt[i].length; j++) {
System.out.print(dt[i][j]+",");
}
System.out.println("<-"+cmnt+":"+i);
}
}
static void show2(ArrayDeque<Long> dt) { //上手くいかなかった時用
long a=0;
while(dt.size()>0) {
a=dt.removeFirst();
System.out.print(a);
}
System.out.println("\n");
}
static void show2(List dt) { //上手くいかなかった時用
for(int i=0; i<dt.size(); i++) {
System.out.print(dt.get(i)+",");
}
System.out.println("\n");
}
private static void prtlnas(int[] as) {
PrintWriter out = new PrintWriter(System.out);
for(int i=0; i<as.length; i++) {
out.println(as[i]);
}
out.flush();
}
private static void prtlnas(long[] as) {
PrintWriter out = new PrintWriter(System.out);
for(int i=0; i<as.length; i++) {
out.println(as[i]);
}
out.flush();
}
private static void prtspas(int[] as) {
PrintWriter out = new PrintWriter(System.out);
out.print(as[0]);
for(int i=1; i<as.length; i++) {
out.print(" "+as[i]);
}
out.println();
out.flush();
}
private static void prtspas(long[] as) {
PrintWriter out = new PrintWriter(System.out);
out.print(as[0]);
for(int i=1; i<as.length; i++) {
out.print(" "+as[i]);
}
out.println();
out.flush();
}
private static void prtspas(ArrayList as) {
PrintWriter out = new PrintWriter(System.out);
out.print(as.get(0));
for(int i=1; i<as.size(); i++) {
out.print(" "+as.get(i));
}
out.println();
out.flush();
}
private static void fill(boolean[] ob, boolean res) {
for(int i=0; i<ob.length; i++) {
ob[i] = res;
}
}
private static void fill(int[] ob, int res) {
for(int i=0; i<ob.length; i++) {
ob[i] = res;
}
}
private static void fill(long[] ob, long res) {
for(int i=0; i<ob.length; i++) {
ob[i] = res;
}
}
private static void fill(char[] ob, char res) {
for(int i=0; i<ob.length; i++) {
ob[i] = res;
}
}
private static void fill(double[] ob, double res) {
for(int i=0; i<ob.length; i++) {
ob[i] = res;
}
}
private static void fill(boolean[][] ob,boolean res) {
for(int i=0;i<ob.length; i++) {
for(int j=0; j<ob[0].length; j++) {
ob[i][j] = res;
}
}
}
private static void fill(int[][] ob, int res) {
for(int i=0; i<ob.length; i++) {
for(int j=0; j<ob[0].length; j++) {
ob[i][j] = res;
}
}
}
private static void fill(long[][] ob, long res) {
for(int i=0; i<ob.length; i++) {
for(int j=0; j<ob[0].length; j++) {
ob[i][j] = res;
}
}
}
private static void fill(char[][] ob, char res) {
for(int i=0; i<ob.length; i++) {
for(int j=0; j<ob[0].length; j++) {
ob[i][j] = res;
}
}
}
private static void fill(double[][] ob, double res) {
for(int i=0; i<ob.length; i++) {
for(int j=0; j<ob[0].length; j++) {
ob[i][j] = res;
}
}
}
private static void fill(int[][][] ob,int res) {
for(int i=0;i<ob.length;i++) {
for(int j=0;j<ob[0].length;j++) {
for(int k=0;k<ob[0][0].length;k++) {
ob[i][j][k]=res;
}
}
}
}
private static void fill(long[][][] ob,long res) {
for(int i=0;i<ob.length;i++) {
for(int j=0;j<ob[0].length;j++) {
for(int k=0;k<ob[0][0].length;k++) {
ob[i][j][k]=res;
}
}
}
}
static 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);
}
public boolean hasNext() {
while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
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 nexL() {
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) || b == ':') {
return minus ? -n : n;
}else{
throw new NumberFormatException();
}
b = readByte();
}
}
public int nexI() {
long nl = nexL();
if(nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nexD() { return Double.parseDouble(next());}
public void al(long[] array) {
for(int i=0; i<array.length; i++) {
array[i] = nexL();
}
return;
}
public void ai(int[] array) {
for(int i=0; i<array.length; i++) {
array[i] = nexI();
}
return;
}
public void aimin1(int[] array) {
for(int i=0; i<array.length; i++) {
array[i] = nexI()-1;
}
return;
}
public void aD(double[] array) {
for(int i=0; i<array.length; i++) {
array[i] = nexD();
}
return;
}
public void ai2(int[] as, int[] bs) {
for(int i=0; i<as.length; i++) {
as[i] = nexI();
bs[i] = nexI();
}
return;
}
public void al2(long[] as, long[] bs) {
for(int i=0; i<as.length; i++) {
as[i] = nexL();
bs[i] = nexL();
}
return;
}
public void ai3(int[] as, int[] bs, int[] cs) {
for(int i=0; i<as.length; i++) {
as[i] = nexI();
bs[i] = nexI();
cs[i] = nexI();
}
return;
}
public void ad2i(int[][] as) {
for(int i=0; i<as.length; i++) {
for(int j=0; j<as[0].length; j++) {
as[i][j] = nexI();
}
}
return;
}
public void ain(int[]... as) {
for(int i=0; i<as[0].length; i++) {
for(int j=0; j<as.length; j++) {
as[j][i] = nexI();
}
}
return;
}
public void aln(long[]... as) {
for(int i=0; i<as[0].length; i++) {
for(int j=0; j<as.length; j++) {
as[j][i] = nexL();
}
}
return;
}
}
static class Graph0n {
private ArrayList<Node0n> dt = new ArrayList<>();
Graph0n(int sz) {
for(int i = 0; i < sz; i++) {
Node0n node1 = new Node0n();
dt.add(node1);
}
}
public void add(int vn, int val) {
dt.get(vn).add(val);
}
public void add2(int vn, int val) {
dt.get(vn).add(val);
dt.get(val).add(vn);
}
public int get(int vn, int index) {
return dt.get(vn).get(index);
}
public ArrayList<Integer> get(int vn) {
return dt.get(vn).getAll();
}
public int size() {
return dt.size();
}
public int sizeOf(int vn) {
return dt.get(vn).size();
}
public void clear() {
for(int i = 0; i < dt.size(); i++) {
dt.get(i).clear();
}
}
public void clear(int i) {
dt.get(i).clear();
}
public static Graph0n make_tree(int vn, FastScanner sc) {
Graph0n tree = new Graph0n(vn);
for(int i = 1; i < vn; i++) {
int s1 = sc.nexI() - 1;
int g1 = sc.nexI() - 1;
tree.add2(s1, g1);
}
return tree;
}
private void add_Vertex(Node0n vnew) {
dt.add(vnew);
}
}
static class Node0n { // 重みなし無向・有向グラフの頂点
private ArrayList<Integer> next_vs = new ArrayList<>();
public void add(int val) {
next_vs.add(val);
}
public int get(int ad) {
return next_vs.get(ad);
}
public ArrayList<Integer> getAll() {
return next_vs;
}
public int size() {
return next_vs.size();
}
public void clear() {
next_vs.clear();
}
public void addAll(Node0n vnew) {
this.next_vs.addAll(vnew.next_vs);
}
}
static class Edge {
int from=-1, v2=-1;
long weight;
public Edge(int vn, long w) {
this.v2 = vn;
this.weight = w;
}
public Edge(int cm, int vn, long w) {
this.from = cm;
this.v2 = vn;
this.weight = w;
}
}
static class Edge2 {
int v2;
long cost1,cost2;
public Edge2(int vn, long w1, long w2) {
this.v2 = vn;
this.cost1 = w1;
this.cost2 = w2;
}
}
static class CompEdge_float implements Comparator<Edge>{
//今は小さいのが前に出てくる
public int compare(Edge a, Edge b) {
if(a.weight>b.weight) return 1;
else if(a.weight<b.weight) return -1;
else return a.v2-b.v2;
}
}
static class Vector {
int x,y;
public Vector(int sx, int sy) {
this.x=sx;
this.y=sy;
}
}
}