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;
	
	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 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 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 3779 Byte
Status AC
Exec Time 449 ms
Memory 21172 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 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