Contest Duration: - (local time) (90 minutes) Back to Home

Submission #172844

Source Code Expand

Copy
```import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";

static void solve()
{
int n = ni();
int[] a = na(n);
int mod = 1000000007;
MontgomeryInt mi = new MontgomeryInt(mod);
long basenum = mi.MR(1*mi.r2);
long baseden = mi.MR(1*mi.r2);
for(int i = 0;i < n;){
if(i == n-1)break;
if(a[i] != -1){
int j;
for(j = i+1;j < n && a[j] == -1;j++);
for(int k = 1;k <= j-i-1;k++){
basenum = mi.MR(basenum*mi.MR((long)(a[j]-a[i]+j-i-1-k+1)*mi.r2));
baseden = mi.MR(baseden*mi.MR((long)k*mi.r2));
}
i = j;
}
}
long num = mi.MR(basenum);
long iden = mi.pow(mi.MR(baseden), mod-2);
out.println(mi.mul(num, iden));
}

public static class MontgomeryInt {
public static final long R = 1L<<31;
public int mod, modp, r2;
public long mrr2;

public MontgomeryInt(int mod)
{
this.mod = mod;
modp = NP(mod, R);
long rr = R%mod;
r2 = (int)(rr*rr%mod);
mrr2 = MR(r2);
}

public long MR(long t)
{
long w = (t*modp&R-1)*mod+t>>>31;
return w >= mod ? w-mod : w;
}

public long mul(long a, long b)
{
return MR(MR(a*b)*r2);
}

public long mul(long... a)
{
long base = MR(a[0]*r2);
for(int i = 1;i < a.length;i++)base = MR(base*MR(a[i]*r2));
return MR(base);
}

public long pow(long a, long n) {
//	 		a %= mod; no need for under 5E10
long ra = MR(a*r2);
long rret = mrr2;
int x = 63 - Long.numberOfLeadingZeros(n);
for(;x >= 0;x--){
rret = MR(rret*rret);
if(n<<63-x<0)rret = MR(rret*ra);
}
return MR(rret);
}

public long powmul(long... a)
{
long base = -1;
for(int i = 0;i < a.length;i+=2){
long ra = MR(a[i]*r2);
long rret = mrr2;
long n = a[i+1];
int x = 63 - Long.numberOfLeadingZeros(n);
for(;x >= 0;x--){
rret = MR(rret*rret);
if(n<<63-x<0)rret = MR(rret*ra);
}
if(i == 0){
base = rret;
}else{
base = MR(base*rret);
}
}
return MR(base);
}

public static int NP(long n, long r)
{
int ret = 0;
for(long i = 1, t = 0;r > 1;){
if((t&1)==0){
t += n;
ret += i;
}
t>>>=1;
r>>>=1;
i<<=1;
}
return ret;
}
}

public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}

private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;

try {
is.mark(1000);
while(true){
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}

private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }

private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
}
return sb.toString();
}

private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
```

#### Submission Info

Submission Time 2014-05-18 18:15:05+0900 C - タコヤ木 uwi Java (OpenJDK 1.7.0) 100 5612 Byte AC 485 ms 21088 KB

#### Judge Result

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
Case Name Status Exec Time Memory
sample_01.txt AC 448 ms 20676 KB
sample_02.txt AC 407 ms 20704 KB
sample_03.txt AC 401 ms 20700 KB
subtask1_01.txt AC 395 ms 20700 KB
subtask1_02.txt AC 391 ms 20704 KB
subtask1_03.txt AC 396 ms 20704 KB
subtask1_04.txt AC 413 ms 20696 KB
subtask1_05.txt AC 423 ms 20696 KB
subtask1_06.txt AC 430 ms 20704 KB
subtask1_07.txt AC 435 ms 20704 KB
subtask1_08.txt AC 426 ms 20692 KB
subtask1_09.txt AC 410 ms 20692 KB
subtask1_10.txt AC 418 ms 20776 KB
subtask1_11.txt AC 402 ms 20700 KB
subtask1_12.txt AC 413 ms 20576 KB
subtask2_01.txt AC 413 ms 20708 KB
subtask2_02.txt AC 407 ms 20700 KB
subtask2_03.txt AC 404 ms 20700 KB
subtask2_04.txt AC 407 ms 20704 KB
subtask2_05.txt AC 444 ms 20680 KB
subtask2_06.txt AC 462 ms 20704 KB
subtask2_07.txt AC 449 ms 20700 KB
subtask2_08.txt AC 444 ms 20712 KB
subtask2_09.txt AC 485 ms 20680 KB
subtask2_10.txt AC 411 ms 20684 KB
subtask2_11.txt AC 417 ms 20704 KB
subtask2_12.txt AC 394 ms 20708 KB
subtask3_01.txt AC 418 ms 20712 KB
subtask3_02.txt AC 392 ms 20704 KB
subtask3_03.txt AC 449 ms 20712 KB
subtask3_04.txt AC 434 ms 20960 KB
subtask3_05.txt AC 435 ms 20700 KB
subtask3_06.txt AC 443 ms 20696 KB
subtask3_07.txt AC 409 ms 20704 KB
subtask3_08.txt AC 440 ms 21080 KB
subtask3_09.txt AC 414 ms 20700 KB
subtask3_10.txt AC 437 ms 21088 KB
subtask3_11.txt AC 402 ms 20696 KB
subtask3_12.txt AC 413 ms 21084 KB