結果

問題 No.148 試験監督（3）
ユーザー uwiuwi
提出日時 2015-02-12 17:47:32
言語 Java21
(openjdk 21)
結果
AC  
実行時間 493 ms / 1,000 ms
コード長 5,958 bytes
コンパイル時間 5,076 ms
コンパイル使用メモリ 81,376 KB
実行使用メモリ 60,744 KB
最終ジャッジ日時 2023-09-06 00:00:03
合計ジャッジ時間 7,874 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 165 ms
53,216 KB
testcase_01 AC 241 ms
53,208 KB
testcase_02 AC 309 ms
53,224 KB
testcase_03 AC 311 ms
52,748 KB
testcase_04 AC 384 ms
52,968 KB
testcase_05 AC 272 ms
53,040 KB
testcase_06 AC 368 ms
57,784 KB
testcase_07 AC 479 ms
60,188 KB
testcase_08 AC 493 ms
60,744 KB
testcase_09 AC 127 ms
55,012 KB
testcase_10 AC 126 ms
53,032 KB
testcase_11 AC 64 ms
50,536 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package q3xx;
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 Q371_4F {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static final int INTERVAL = 2000000;
	
	static int d(char[] a,int l){int r=0,j=l+4;for(;j>=l;j--)r=r*93+a[j]-(a[j]+1880)/58;return r;}
	static final char[] enigma = "!    cTce(f$*L$NT-6%r9PB$0fO,*B5:;!U#$7#BJlN%QosC)6;TU'[<DU(A$4! 9cvR)R+/9 $](#!K8-9,<0FN'$5G:(Yr<a+srr`*eGY^*r9>?%Tl`?&o=7y$Ljeu O;6[#'Ss%$p*y2+!6)q+s?#C 0txk qrT7+km`/!dhrT%1]bB)Et$m+f?Wn(rvjo%9duz(*5P`#Y'bg(YMs-'Jbas&.)$#-Pb%s,Y.cp* <v.!)# h O>|8#FnUF-^M2O-Sm8W(foqX !Ux[ u+Hi$:m*9*~wb2 O>_A&PeI]&~#&p).l+8#ztE:(dS m(zZz$+U63@);^J8$r&_l 4/2<&&lB-#]+ |-'XbQ'v}'*!3M6r'K@y! R>{N$V+o>%Gx*y&n C(!v8ft)9gRZ#&T8,' !fp#-|n&,71T&*CaTt YRkY#f6V`%F(l+!SWqb w;s>(!%/a%Gg?{$N#Z= GL] +nUTL!!U8G!P1C8(G4pA%H[ I)?.7M-u{)3$aDqJ(r*JA,EB1C-0({a*@b~1$F6c0-vZ{V''sw/,a?_x%Ameu*iK*j+X#}<#{7ST!;66X$jws8$7nmI'5&@:!-`PS!PH+n!SjXO*&POu%r2|Y$6'='!J`eO!YL,D!x~#S%$)_J!kkwF'5?Km!06mu(V6;e%[Z,6,[7Ap*OVKv#$8I:)SyN)&O1+!-%j4e >yBY&5DG.#IAy7.+2A#'nVp`)(FWb'A8TQ AOA/'u#^0'Cd2Y)x][x)Z3: **WM`#E.T8,=yjg'bhfd!HEy~$Pq>e(lD:@+|`&f#RWPG --Pq%Rz{>'<[%q(1/5Y+vS#}'Qy~M%*4n='1'xI%])Y4'wJ6-%/M?h(zu(i-yaJ|,-YA2,XZw/&:rAa*S(5U*vOW*,CQ%w <t9R#fM1Z-8T?p+j,o#,'ka0.vw^}!<=dk,:D&D*Gm`$%Avg5$;c@V-i5LA%mNBS!212w#XxjF#,U.9->a4n&_:1]&UbJl 0n*'!.5bf&Q;L6%!5&V-#i;V-'C<.,DnK>.*+<?*^1t_$V~GC-8]+z,rptk%!LAj(5`K]%pQp`!8lu=$jb]X(mu-l#2<|~!L6?-%P=$Q$S5mH+9Zn7.)%G(#B![P*Iw/$'`U02'^Hog)Mh}T ;[O#*!yQN-%l!a$t%2B%N)}C$2etG()jp(+!4B/-&OWZ*KIBa&};u` >`+_##L??!aI3~*X&-^'Kdnd*8+;{$?(NF*#L,l*NgBA P}Bu#lgkd%e5cl*K=f.'0>a5 :4Iw PHQF&y.[=!~McG oaTT,:b^7#V&9Y*sEv-)ua,/&2zV+*jN<2%q*Ow&s4JH$jFGP)=wSE(,cr;-wW.C%!3?u!n5y9*;#{N#99~T(Buey'UI'>*J3vz%;5t6-VZT@-D5+F+3m*R)n1#U'ke#2'HS4a+5D|A*M]|p+rXM+)Mz`E#~XYk'x'X&+NxFA,4r%L sDxn&,?nj#C!Qh#2Unh!&6O`)U|' (~>/@ )3sx+yl`a*Z4'D*r|[h$jQ.}(mjk%%0x0^$Y,c^ b?OU-`e?^ i6<M'A]NB%'9 y)rKRv-iiPm%}N/K&,J**'#t/`!Ne(=--P[L'Lce6#Z+5(-wR^w%8w:3&02h?$`jJ>%W[b6!]=B4 ej/z*Iu]L%L5:>!)~#<+kd0s,IR@k(bS%<-lRc2.NR^~%5R?I$P]iE*aZ.,%L-5G#lrb*)Uf;_$Lw+,*{&1_-{;Ud'#Vg$,cA-D*BcvU%=,mu+Y(/_ W4yl-f>FM-CbBQ%qu.[,$YOK)vFvn&>p.f!QV%',Ajw:-u7)?(Q^YE,2>n4*fVzV(z{Yp#ZsJF&9p]r)VMKh#&RnR'#b|g$)Q6.(w$W!&9Te?-ZZHy#n]UC*-]vR,'oQv#z8co+Hs,>$bMqq+AUgK,S5{@)WO4T(X%NF'n.M''YqC^ g3,})I<Xl'c.D~,Xf0x,&J9d$=yEA)/4Em+csy{,6GjF)X%H<-m~U +{i1a(.mz<#&ooi(]W-4 ,+Zd#kiui,MqU2.XG'S$=|xO+/H'`&#m&>*[tA0#OTf6(aXC8,T'|G)[x-Y$l3J#!;9V]&KVd$+:2P~)#NiX'8OY@!5,7T)VQ'I-,tIt+XZjH&BhP- '~ /.?m)C(e96!,?NZ^-zn%9,H5hz,Lpco,Y-%U!j|.6$1DAi$S@xR(`M$B+RPqH$U}A;-eOk'+~,g'%zjY/#Ie>E)V'ca+|6Aw+0:UQ+X>jC*P{V;$Z2#. pT+/+@T V'S$AR!>$)p(~OGY*5:ft dF{b%_eBY'Dv|<#mk s%/^Uv-KQ&V!Wyk0$K*wW#fh3I!uF9Y+1#|/$BMY2 `@KG+oEF_ [ReN,W,gR*x+w@-xz9,!o'/v#tw C#S]}F!M |- wCg4%w/OL*v*;^-9Fhh$&J0H NDbv-Ny/8-w'p#-qz>q'v)IZ!MyWW'ToZ4#1X)9-m+!w*igG1(Au*%&~z'O,0Y;~%[pk ,u1y| $vb?,2Fy])t0%h#pwmI+(=h~(N[R@*]\r\n".toCharArray();
	static void solve()
	{
		for(int T = ni();T >= 1;T--){
			String C = ns(), P = ns();
			if(P.length() >= 11){
				out.println(0);
				continue;
			}
			long pl = Long.parseLong(P);
			
			if(pl >= mod){
				out.println(0);
				continue;
			}
			
			long cl = 0;
			if(C.length() >= 12){
				for(char x : C.toCharArray())cl = (cl*10+x-'0')%mod;
			}else{
				cl = Long.parseLong(C);
				if(cl-(2*pl-1)+1 <= 0){
					out.println(0);
					continue;
				}
			}
			
			long sup = (cl-(pl-1))%mod;
			long inf = (cl-(2*pl-1))%mod;
			if(inf < 0)inf += mod;
			if(sup < 0)sup += mod;
			if(sup < inf){
				out.println(0);
				continue;
			}
			
			out.println(f((int)sup)*invl(f((int)inf), mod)%mod);
		}
	}
	
	public static long invl(long a, long mod) {
		long b = mod;
		long p = 1, q = 0;
		while (b > 0) {
			long c = a / b;
			long d;
			d = a;
			a = b;
			b = d % b;
			d = p;
			p = q;
			q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}
	
	static long f(int n)
	{
		int h = n%INTERVAL;
		if(h < INTERVAL/2){
			long mul = d(enigma, n/INTERVAL*5);
			int base = n/INTERVAL*INTERVAL;
			for(int i = base+1;i <= n;i++){
				mul = mul * i % mod;
			}
			return mul;
		}else{
			long mul = 1;
			int base = n/INTERVAL*INTERVAL+INTERVAL;
			for(int i = base;i > n;i--){
				mul = mul * i % mod;
			}
			return invl(mul,mod)*d(enigma, n/INTERVAL*5+5)%mod;
		}
	}
	
	static int mod = 1000000007;
	
	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 boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	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)); }
}
0