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

Submission #172850

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);
final int mod = 1000000007;
MontgomeryInt mi = new MontgomeryInt();
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 final int mod = 1000000007;
public final int modp = 79133769;
public final int r2 = 145586002;
public final long mrr2 = 147483634;

public MontgomeryInt()
{
}

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) {
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 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 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 void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
```

#### Submission Info

Submission Time 2014-05-18 18:23:45+0900 C - タコヤ木 uwi Java (OpenJDK 1.7.0) 100 3779 Byte AC 449 ms 21172 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 426 ms 20656 KB
sample_02.txt AC 410 ms 20788 KB
sample_03.txt AC 405 ms 20660 KB
subtask1_01.txt AC 412 ms 20652 KB
subtask1_02.txt AC 406 ms 20656 KB
subtask1_03.txt AC 410 ms 20660 KB
subtask1_04.txt AC 413 ms 20660 KB
subtask1_05.txt AC 410 ms 20788 KB
subtask1_06.txt AC 404 ms 20652 KB
subtask1_07.txt AC 402 ms 20652 KB
subtask1_08.txt AC 404 ms 20780 KB
subtask1_09.txt AC 404 ms 20660 KB
subtask1_10.txt AC 404 ms 20704 KB
subtask1_11.txt AC 412 ms 20664 KB
subtask1_12.txt AC 403 ms 20664 KB
subtask2_01.txt AC 406 ms 20660 KB
subtask2_02.txt AC 449 ms 20732 KB
subtask2_03.txt AC 408 ms 20660 KB
subtask2_04.txt AC 407 ms 20660 KB
subtask2_05.txt AC 401 ms 20792 KB
subtask2_06.txt AC 402 ms 20660 KB
subtask2_07.txt AC 410 ms 20792 KB
subtask2_08.txt AC 408 ms 20656 KB
subtask2_09.txt AC 402 ms 20664 KB
subtask2_10.txt AC 408 ms 20660 KB
subtask2_11.txt AC 407 ms 20652 KB
subtask2_12.txt AC 414 ms 20656 KB
subtask3_01.txt AC 404 ms 20788 KB
subtask3_02.txt AC 402 ms 20784 KB
subtask3_03.txt AC 398 ms 20656 KB
subtask3_04.txt AC 412 ms 21044 KB
subtask3_05.txt AC 403 ms 20660 KB
subtask3_06.txt AC 436 ms 20788 KB
subtask3_07.txt AC 406 ms 20660 KB
subtask3_08.txt AC 419 ms 21048 KB
subtask3_09.txt AC 408 ms 20656 KB
subtask3_10.txt AC 419 ms 21172 KB
subtask3_11.txt AC 412 ms 20656 KB
subtask3_12.txt AC 422 ms 21048 KB