ソースコード 拡げる

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 {
INPUT_PATH == null ? System.in : new FileInputStream(new File(INPUT_PATH))));

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) {
brPos = 0;
}
return brBuf[brPos++];
}

private int readInt() throws IOException {
}

private long readLong() throws IOException {
}

private int[] readIntArray() throws IOException {
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 {
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 {
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));
}
static PrintWriter pw = new PrintWriter(System.out);

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

#### 提出情報

提出日時 2014-05-17 23:32:50+0900 C - タコヤ木 tochukaso Java (OpenJDK 1.7.0) 100 7260 Byte AC 715 ms 24388 KB

#### ジャッジ結果

 AC × 3
 AC × 14
 AC × 26
 AC × 36
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
ケース名 結果 実行時間 メモリ
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