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){
				int b = is.read();
				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;
	
	private static int readByte()
	{
		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);
			b = readByte();
		}
		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;
			b = readByte();
		}
		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;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	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;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Submission Time
Task C - タコヤ木
User uwi
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 5612 Byte
Status AC
Exec Time 485 ms
Memory 21088 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 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