Submission #172536


Source Code Expand

Copy
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

import java.math.*;
import java.io.*;
import java.text.*;
import java.util.*;
 
public class Main {
//    private static final String INPUT_PATH = "C:\\atcoder\\b_008_004.txt";
    private static final String INPUT_PATH = null;

    int D = 1000000007;
    public void solve() { 
        try {
            br = new BufferedReader(new InputStreamReader(
                    INPUT_PATH == null ? System.in : new FileInputStream(new File(INPUT_PATH))));

            int N = readInt();
            int[] tA = readIntArray();

            int before = tA[0];
            int cnt = 0;
            long max = 1;
            for (int i = 1 ; i < N; i++) {
                cnt ++;

                if (tA[i] != -1) {
                    int next = tA[i] - before;
                    long patern = 1;
                    long x = next + cnt;
                    
                    long[] dx = new long[cnt - 1];
                    
                    for (int j = 1; j < cnt; j++) {
                        dx[j -1] =  x - j ;
//                        patern = patern * ( x - j ) / (j) % D;
                    }
                    
                    for(int j = 2; j < cnt; j++) {
                        long div = j;
                        for (int k = 0; k < cnt - 1; k++) {
                            long divin = gcd(dx[k],div);
                            if (divin > 1) {
                                div /= divin;
                                dx[k] /= divin;
                                if (div == 1) {
                                    break;
                                }
                            }
                        }
                    }

                    for (int j = 0; j < cnt - 1; j++) {
                        patern = patern * dx[j]  % D;
                    }

                    max = (max * patern) % D;
/**
                    
                    System.out.println(patern % D);
                    
                    long[][] dp = new long[next + 1][cnt + 1];
                    dp[0][0] = 1;
                    for (int j = 0; j < next; j++) {
                        for (int k = 0; k < cnt; k++) {
                            dp[j + 1][k + 1] = max(1, dp[j + 1][k] + dp[j][k + 1]);
                        }
                    }
                    System.out.println(dp[next][cnt]);
                    max = (max * dp[next][cnt]) % D;
**/
                    before = tA[i];
                    cnt = 0;
                }
            }
            
            pw.println(max);
            
            
        } catch(Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
            } catch (Exception igunore) {}
        }
    }

    boolean deepEquals(int[] i1, int[] i2) {
        if (i1.length != i2.length) return false;
        for (int i = 0 ; i < i1.length; i++) if (i1[i] != i2[i]) return false;
        return true;
    }
    String getKey(int[] i) {
        StringBuilder sb = new StringBuilder();
        for (int s : i) sb.append(" " + s);
        return sb.toString();
    }

    private int brPos = 0;
    private int[] brBuf = null;
    
    private int readBufInt() throws IOException {
        if (brBuf == null || brBuf.length == brPos) {
            brBuf = readIntArray();
            brPos = 0;
        }
        return brBuf[brPos++];
    }

    private int readInt() throws IOException {
        return Integer.parseInt(br.readLine());
    }

    private long readLong() throws IOException {
        return Long.parseLong(br.readLine());
    }

    private int[] readIntArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        int[] out = new int[cnt];
        for (int i = 0; i < cnt; i++) out[i] = Integer.parseInt(s[i]);
        return out;
    }

    private Integer[] convIntArray(int[] arg) {
        int len = arg.length;
        Integer[] res = new Integer[len];
        for (int i = 0; i < len; i++) res[i] = arg[i];
        return res;
    }
    
    private long[] readLongArray() throws IOException {
        String[] s = readStrArray();
        int cnt = s.length;
        long[] out = new long[cnt];
        for (int i = 0; i < cnt; i++) out[i] = Long.parseLong(s[i]);
        return out;
    }

    private String[] readStrArray() throws IOException {
        String[] s = br.readLine().split(" ");
        return s;
    }

    void permutationAll(int[] p) {
        permutation(p, 0, p.length - 1);
     }
    
    void permutationRange(int from, int to) {
        int cnt = to - from + 1;
        int[] elements = new int[cnt];
        for (int i = 0 ; i <  cnt; i++) elements[i] = from++;
        permutation(elements, 0, cnt - 1);
    }

    void permutationString(String element) {
        char[] elements = element.toCharArray();
        permutationString(elements, 0, elements.length - 1);
    }

    
    void permutation(int[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 

            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            int tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutation(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    void permutationString(char[] elements, int nowCnt, int totalCnt) {
        if (nowCnt == totalCnt) { 
            
            // TODO insertCode
        } else {
            
          for (int i = nowCnt; i <= totalCnt; i++) {
            char tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
            permutationString(elements, nowCnt+1, totalCnt);
            tmp = elements[nowCnt]; 
            elements[nowCnt] = elements[i]; 
            elements[i] = tmp;
          }
        }
     }

    private static long gcd(long n1, long n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }
    private static int gcd(int n1, int n2) {
        return (n2 == 0)?n1:gcd(n2, n1%n2);
    }

    public static void main(String[] args) {
        long from = System.currentTimeMillis();
        Main app = new Main();
        app.solve();
        pw.flush();
        pw.println(System.currentTimeMillis() - from);
    }

    void printMatrix(int[][] p) {
        for (int[] i : p) printArray(i);
    }
    
    void printArray(int[] p) {
        for (int i : p) System.out.print(i + " ");
        System.out.println();
    }

   void debug(Object ... o) {
       pw.write(deepToString(o));
   }
   BufferedReader br = null;
   static PrintWriter pw = new PrintWriter(System.out);

   class Type {
       int x, y;
       Type (int x, int y) {
           this.x = x;
           this.y = y;
       }
   }
}

Submission Info

Submission Time
Task C - タコヤ木
User tochukaso
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 7260 Byte
Status AC
Exec Time 715 ms
Memory 24388 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 410 ms 20792 KB
sample_02.txt AC 386 ms 20784 KB
sample_03.txt AC 386 ms 20656 KB
subtask1_01.txt AC 388 ms 20784 KB
subtask1_02.txt AC 388 ms 20652 KB
subtask1_03.txt AC 392 ms 20780 KB
subtask1_04.txt AC 388 ms 20788 KB
subtask1_05.txt AC 391 ms 20784 KB
subtask1_06.txt AC 415 ms 20664 KB
subtask1_07.txt AC 406 ms 21100 KB
subtask1_08.txt AC 415 ms 20656 KB
subtask1_09.txt AC 404 ms 20656 KB
subtask1_10.txt AC 398 ms 20792 KB
subtask1_11.txt AC 411 ms 20788 KB
subtask1_12.txt AC 396 ms 20716 KB
subtask2_01.txt AC 405 ms 20668 KB
subtask2_02.txt AC 392 ms 20780 KB
subtask2_03.txt AC 396 ms 20656 KB
subtask2_04.txt AC 407 ms 20784 KB
subtask2_05.txt AC 414 ms 20924 KB
subtask2_06.txt AC 390 ms 20788 KB
subtask2_07.txt AC 559 ms 23300 KB
subtask2_08.txt AC 402 ms 21692 KB
subtask2_09.txt AC 422 ms 21420 KB
subtask2_10.txt AC 421 ms 21796 KB
subtask2_11.txt AC 402 ms 21796 KB
subtask2_12.txt AC 416 ms 21684 KB
subtask3_01.txt AC 393 ms 20788 KB
subtask3_02.txt AC 389 ms 20656 KB
subtask3_03.txt AC 390 ms 20660 KB
subtask3_04.txt AC 419 ms 22084 KB
subtask3_05.txt AC 391 ms 20784 KB
subtask3_06.txt AC 416 ms 21556 KB
subtask3_07.txt AC 715 ms 23296 KB
subtask3_08.txt AC 437 ms 24288 KB
subtask3_09.txt AC 407 ms 21684 KB
subtask3_10.txt AC 436 ms 23460 KB
subtask3_11.txt AC 424 ms 21672 KB
subtask3_12.txt AC 435 ms 24388 KB