結果
問題 | No.1141 田グリッド |
ユーザー | CaliPota |
提出日時 | 2020-07-31 22:15:45 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 270 ms / 2,000 ms |
コード長 | 20,372 bytes |
コンパイル時間 | 3,638 ms |
コンパイル使用メモリ | 91,844 KB |
実行使用メモリ | 62,468 KB |
最終ジャッジ日時 | 2024-07-06 18:34:58 |
合計ジャッジ時間 | 10,039 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
49,992 KB |
testcase_01 | AC | 49 ms
50,460 KB |
testcase_02 | AC | 47 ms
50,428 KB |
testcase_03 | AC | 47 ms
50,264 KB |
testcase_04 | AC | 46 ms
49,988 KB |
testcase_05 | AC | 48 ms
50,288 KB |
testcase_06 | AC | 47 ms
49,916 KB |
testcase_07 | AC | 47 ms
49,928 KB |
testcase_08 | AC | 53 ms
50,348 KB |
testcase_09 | AC | 51 ms
50,072 KB |
testcase_10 | AC | 56 ms
50,280 KB |
testcase_11 | AC | 68 ms
50,632 KB |
testcase_12 | AC | 57 ms
50,508 KB |
testcase_13 | AC | 270 ms
62,468 KB |
testcase_14 | AC | 257 ms
59,340 KB |
testcase_15 | AC | 236 ms
58,196 KB |
testcase_16 | AC | 257 ms
62,216 KB |
testcase_17 | AC | 253 ms
58,120 KB |
testcase_18 | AC | 170 ms
57,504 KB |
testcase_19 | AC | 166 ms
57,556 KB |
testcase_20 | AC | 166 ms
57,460 KB |
testcase_21 | AC | 244 ms
57,928 KB |
testcase_22 | AC | 244 ms
58,004 KB |
testcase_23 | AC | 242 ms
58,028 KB |
testcase_24 | AC | 170 ms
58,972 KB |
testcase_25 | AC | 175 ms
58,980 KB |
testcase_26 | AC | 177 ms
57,660 KB |
testcase_27 | AC | 167 ms
55,524 KB |
testcase_28 | AC | 175 ms
59,132 KB |
testcase_29 | AC | 170 ms
59,092 KB |
testcase_30 | AC | 169 ms
57,600 KB |
testcase_31 | AC | 169 ms
57,748 KB |
testcase_32 | AC | 169 ms
57,836 KB |
testcase_33 | AC | 169 ms
58,020 KB |
ソースコード
import java.util.*; import java.io.*; import java.math.*; public class Main { 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 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; } } 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(); } } 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 Comparator_Edge 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; } } //私が好きなアルゴリズム::累積和・UF木 //PriorityQueueは拡張for文で出すとsortされてない順番で出てくるよ //longのbit演算は1L<<posに注意 //long long //JOIはMLEが厳しい shortというものがあるよ。 public static void main(String[] args) throws Exception { FastScanner sc = new FastScanner(); PrintWriter out = new PrintWriter(System.out); int h = sc.nexI(); int w = sc.nexI(); long[][] as = new long[h][w]; long all_product = 1L; long[] rowprdct = new long[h]; long[] colprdct = new long[w]; fill(rowprdct,1L); fill(colprdct,1L); int n0 = 0; int[] rn0 = new int[h]; int[] cn0 = new int[w]; fill(rn0,0); fill(cn0,0); for(int i=0; i<h; i++){ for(int j=0; j<w; j++){ as[i][j] = sc.nexL(); if(as[i][j]==0){ n0++; rn0[i]++; cn0[j]++; }else{ all_product *= as[i][j]; all_product %= e97; rowprdct[i] *= as[i][j]; rowprdct[i] %= e97; colprdct[j] *= as[i][j]; colprdct[j] %= e97; } } } int q = sc.nexI(); for(int t=0; t<q; t++){ int r2cut = sc.nexI()-1; int c2cut = sc.nexI()-1; int n0ofrc = rn0[r2cut]+cn0[c2cut]; if(as[r2cut][c2cut]==0) n0ofrc--; if(n0ofrc == n0){ long ans = all_product; ans *= modinv(rowprdct[r2cut], e97); ans %= e97; ans *= modinv(colprdct[c2cut], e97); ans %= e97; if(as[r2cut][c2cut]>0) ans *= as[r2cut][c2cut]; ans %= e97; out.println(ans); }else{ out.println(0); } } out.flush(); } private static int INF = (int)1e8; private static long INFL = (long)1e17; private static long e97 = (long)1e9 + 7; private static void assertion(boolean b) { if(!b) throw new AssertionError(); } 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 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 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 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=INF; 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=INFL; 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=INF; 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=INFL; 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=-INF; 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=-INFL; 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=-INF; 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=-INFL; 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 =0; for(long e: dt){ sum += e; } return sum; } private static int sumA(List<Integer> dt){ int sum =0; for(long e: dt){ sum += e; } return sum; } private static boolean same3(long a, long b, long c){ if(a!=b) return false; if(b!=c) return false; if(c!=a) return false; return true; } private static boolean dif3(long a, long b, long c){ if(a==b) return false; if(b==c) return false; if(c==a) return false; return true; } private static boolean triangle_inequality(int a, int b, int c){ if((a+b)<c) return false; if((b+c)<a) return false; if((c+a)<b) return false; return true; } private static double hypod(double a, double b){ return Math.sqrt(a*a+b*b); } private static long factorial(int n) { long ans=1; for(long i=n; i>0; i--){ ans*=i; } return ans; } private static long facP(int n, long p) { long ans=1; for(long i=n; i>0; i--){ ans*=i; ans %= p; } return ans; } private static long lcm(long m, long n){ long ans = m/gcd(m,n); ans *= n; return ans; } private static long gcd(long m, long n) { 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) { //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 < 0) u += p; return u; } private static int pow(int n, int k){ int ans=1; for(int i=0; i<k; i++) ans *= n; return ans; } private static long pow(long n, int k){ long ans=1; for(int i=0; i<k; i++) ans *= n; return ans; } 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はd桁の数で、2^dより小さい } private static int getDigit10(long num){ long cf = 1; int d=0; while(num >= cf){ d++; cf*=10; } return d; //numはd桁の数で、10^dより小さい } private static boolean isINF(int in){ if(((long)in*20)>INF) return true; else return false; } private static boolean isINFL(long in){ if((in*10000)>INFL) return true; else return false; } private static long pow10E97(long ob, long soeji, long p){ if(ob==0) return 0; if(soeji==0) return 1; if(soeji==2) return (ob*ob)%p; int d = getDigit2(soeji); 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=1; for(int i=d-1; i>=0; i--){ if(soeji >= (long)(1<<i)){ soeji -= (long)(1<<i); ans = (ans*ob_pow_2pow[i])%p; } } return ans%p; } private static long nC2(long n){ return ((n*(n-1))/2L); } private static int divceil(int numerator, int denominator){ return (numerator+denominator-1)/denominator; } private static long divceil(long numerator, long denominator){ return (numerator+denominator-1L)/denominator; } private static int iflag(int pos){ return (1<<pos); } private static long flag(long pos){ 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)) > 0) return true; else return false; } private static int deflag(int bit, int pos){ return bit&~(1<<pos); } private static int countFlaged(int bit){ int ans=0; for(int i=0; i<getDigit2(bit); i++){ if((bit&(1<<i)) > 0) ans++; } return ans; } private static int countFlaged(long bit){ int ans=0; for(long i=0; i<getDigit2(bit); i++){ if((bit&(1L<<i)) > 0) ans++; } return ans; } 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(); } 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; } public static int biSearchMax(long[] dt, long target){ int left=-1, right=dt.length; int mid=-1; while((right-left)>1){ mid = left + (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(); int mid=-1; while((right-left)>1){ mid = left + (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; } static void show2(boolean[][] dt, int lit_x, int lit_y){ PrintWriter out = new PrintWriter(System.out); for(int j=0; j<dt.length; j++){ for(int i=0; i<dt[j].length; i++){ if((i==lit_y) && (j==lit_x)) out.print("X"); else if(dt[j][i]) out.print("O"); else out.print("."); } out.println(); } out.flush(); } static void show2(int[][] dt, String cmnt){ PrintWriter out = new PrintWriter(System.out); for(int i=0; i<dt.length; i++){ for(int j=0; j<dt[i].length; j++){ out.print(dt[i][j]+","); } out.println("<-"+cmnt+":"+i); } out.flush(); } static void show2(long[][] dt, String cmnt){ PrintWriter out = new PrintWriter(System.out); for(int i=0; i<dt.length; i++){ for(int j=0; j<dt[i].length; j++){ out.print(dt[i][j]+","); } out.println("<-"+cmnt+":"+i); } out.flush(); } 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(List 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 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(); } } } 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(); } } } } }