結果

問題 No.148 試験監督(3)
ユーザー uwiuwi
提出日時 2015-02-09 23:50:42
言語 Java21
(openjdk 21)
結果
AC  
実行時間 390 ms / 1,000 ms
コード長 10,569 bytes
コンパイル時間 2,350 ms
コンパイル使用メモリ 81,612 KB
実行使用メモリ 58,424 KB
最終ジャッジ日時 2024-06-23 16:51:51
合計ジャッジ時間 5,902 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 126 ms
51,488 KB
testcase_01 AC 183 ms
51,428 KB
testcase_02 AC 190 ms
51,480 KB
testcase_03 AC 252 ms
51,208 KB
testcase_04 AC 297 ms
51,348 KB
testcase_05 AC 258 ms
51,220 KB
testcase_06 AC 318 ms
57,864 KB
testcase_07 AC 369 ms
58,424 KB
testcase_08 AC 390 ms
58,408 KB
testcase_09 AC 159 ms
54,976 KB
testcase_10 AC 156 ms
55,232 KB
testcase_11 AC 72 ms
50,876 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

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 final int INTERVAL = 700000;
	
	static int dec(char[] a,int l,int r){int ret=0;for(int i=r-1;i>=l;i--)ret=ret*93+ord(a[i]);return ret;}
	static int[] decs(char[] a){int[] ret=new int[a.length/5];for(int i=0,j=0;j<a.length;i++,j+=5)ret[i]=dec(a,j,j+5);return ret;}
	static int ord(char c){return c-(c<='!'?0:c<='['?1:2)-32;}
	static final int[] fs = decs("!    YH5$(9X<4(3cK'${7AQ,%9zH-WbK;(oOE>$KR^G'a_&e)Vv|5*Q)yP&qRZy#/:S?$mf!D'_lr**C{s}%r8H/+q9,Z(E~RI+U#$7#Q_It,$Hn8+WHN@'LQ2D,Zmox,EXGX,F=ke)P~DG'[r]](NP!;$K-$`'N#C<({NxU#1j50)]oy* O2<).o7Uw-;A%i$I0:1!R+/9 |P|z%[3=]'1(Tx#F^RD @EtF py~_-OiPd i<w<*~' u(B1`3'l]Zi),0PB(K]%;+{c!7'?a)m%y;lA-27Vp-o1<w'Kb3+*eGY^*bl'F-[_U &U1'< J0C4!XJSq#>t>#*{nu6#ZWcR!i9@D!wJgs+]Ju[')Qr5 3C?P$V##P(BfId*z'3F+Jh.0,f ,c 9/q%'p*y2+hqbL++OBi){{BQ+Qw;K%a=V*%#k}P(.oZM'%:,m,33rZ hkH( GUEl-2Jmq+dB 3%5j9G(2d$o&N#+a*0EBU PB/_**u>|*1]bB)r^BN-1{-k%Uc<L-$tj:(Y? M&kQ_]&&V7I!*DkH-xM`j$I:aH'!;=M,9eRx*{PnD!N[m:''p+G#@x6:$^'0@$cgUZ$<Lpa,YMs-'zD2l!>:x!$QbK}']`.p#|PuA)/tTZ!p;fV'oHX`+5FR$ UGci)eT^K$2mw-(N'dv!fdI5,YnSk+`'Fa!z`rq,Xr$I,M_KT'O>|8#OiJ(*v-'r 'K:}+. %,! lCR#$M].+>J*~#h:V,.Z0Xd(b<TO!?&y9,h*XJ,[Sqp&nT5$#vjUn+!q'_'MbmK#%S)r!m6Q6$:m*9*48q$!&s$9#W-[V)8DIU+H-*@#g%qr-/u+=$<lI]*m4K5$T#^y#Ej]K(K.1X+A&Qi#07m#&3-P0,6EI>+Odxt#IwTu&:B!-(dS m(lnGG'5*!|!mR'/*W'GO*ZU6a!sN{/,C#4('[mf}&h{;f,x=aG(L M_#3E<j*wYUV'sqMb!~WIn&-F]I+Zg0;)`A+f+r{uK#]+ |-?r2(-l,4!'Q}Ao'ii|n(?=#F gk77,Dv:~*&0FA#3{Z#,t~M9$vQRo+Xh|@ whn> D~u])8tQg-SKHs&_{>z!JVvG$wD}K,Gx*y&<k2]+,n2+!zq~?,u,B4)MY4? 2'2q#EdI]%>QwZ$[,EM%]Z)d(Zq31+9(r<)M2v+)YT76*h5Ly(oxgJ('{0..Fo39)?kZV*71T&*2wpF%e=f)!y&3A)}xf8# vD**{nsg'pz68%5zz] SO0G* %(O+.HMR,;FZz)+8 Y-Sa>W e,p_'e*qA FK|:,>*7D!Q-En$!%/a%$> |$?Z$4)V?d'$nDZ$%Q#3n+vM{w !$%g!<~X5%Pqw$ m<wO#R *x%(9A&.f~ Z(`%oi)2}.&+q3?r-=5d|&JI_R,+eOk&G4pA%wl.[#nm*C#I9!T&!T69$>7s0)X3??&!vW9)@T&Y#AGNa ?zgo'Tr}R%sL]} yaI5,54Kz,F&z]$|(`}+eKE+& NP,.e]@a 0({a*3p<&#lW'k!y7R(*6>`2'%_b+';3iS)]n'p bWT}&N]ly!Pwx!'mv9B+6U[_+[U.4):Vq7!bRKd!];:I+,wnE+~P8T)X[Xf)iK*j+YSRo!xc(i#3~3O'O/O&*DTfX%u&Z7*>VzF)9ewf+{4*r-k&&?#O,@f#:y- %Oyn7$~>c2+Nz_&+-LL:#I&mE!UsHj%T<Rf)-`PS!*l:l-)nxX&q4r-#gUp8 A@T?.qo#Y#G?bs*'_dy-3~(`#BV,T(*Yl|*wcSR sK3I(M@.Q%Y?/v%Y}m{(Y;?o ?i~| ?,#;%YL,D!s:MQ, Hv|)`.Fd&w:uK'^N1)'3(kF&2VZ.&E.t?%?kJC+}>u[$=HI4&Qub^+%,4t)gOrx%(DbS!~ru4-5+DA q~Ba#vWY~ [Z,6,q6-j'T2nu'&@@% h;`-!M Z;,:Qe6+I]Yv+&I<n$BA^&!7pQJ#*y]T&w$CH+?Hq!']AjD+kzW|-0J!0(GQ^2)}uRE!Ym3R,>yBY&[T'p+<7Br){i+E-c5?t!N2pt-?a&;'^%2H)_vvC$7PGd&x`g>#gn_R*hCR@%U#&< b(7B O@6D#Thk?))q!n)3(;6*_;a9$AOA/'EG6/*!<sa+*;ci&e}A`)|A4F){OAU (PXN!8s.U+^%A] @Vd1*.Z`#(jA}l#xx1%&' pv&r;3T$;#Q4${l@<&DcA`-l'Jy*=yjg'@ZMI%9kR=*g*ao-D*mE%4 E@-G,]0,>.lu!//_B&+0t5.|>R9%M-cL&u~PJ,-7ZA)31ap'wri8+QGuB$B.g^,lNPH*L-UM$--Pq%vqA $d{v: rjP@)]{g=,95vZ)Yqt.'$ZAY)=^GJ-$'M('>>bu$FLNo cm5J'/9'@&txI=%GTmD, Sn]%+1:S)o/fZ(gKH7.1'xI%GKdp,<A(q#LH?&+~PD3)AH6n L(V@-Zel$ DwEH,{sQ.![YvR(BRKB-r(G}+<XI2(_qmH-b<22'Z)]/-C!V5'obql$OQ'c%XZw/&xx @)!}8R,9;6H'IS6Q'q+0d*/L7D*/~Kj+k*zq(Ps%[%`O],&WF@h*oDhx-('>Z+i!=/*utqY%4yn5+xy_R!^fT#)JV^l&8T?p+6gql,L5en*).+D-M772+xB_Y,aoN6 p|bO(nJEQ+>m+,)dBi.#e_t=+au|>$2;IL,err|%gU%<(Ol-? x*T3-X}/B-cuqQ-Avg5$E)3U'51p(-Ys8j(lFw*#cvFx$Mu_f#^@OY&2=|4%GUGF @Ry?'0m+y#zbfL-}R6M)pcSa';ht  Okf0%=_OK! z3a+bm)<%>a4n&GFE[ ,#^I$ 51w%}t&_$9ZKc!cpT'(]W/h&_/@' zK.n& ;=U*<]@6 VI;0%sf!$##o4D!ljWc =P!Z!s[(m&4(V(']JTP-#i;V-ED%~'~D~x'LnM{$[/|# qM{U#$LbO TZPX$69CW'9S;*%f#wO)VXLP$mGPQ&A*ab(iuYj#z[q,'P$~|+B!^Z#R%YY*{n6-*rptk%WGl=$pZ6%#Zj*a,yE.5*qb=@*}-sm*PM..*kp2;,c,?X'[I}d-Vs%S$W@9`-c6%0'uhmk#F2yG%(iYy,=E~F$;6nG)7_hF#2<|~!%fsZ-Rz'_+K R4-U+qp+T4~0,L5|U!76!:./X?Y-s.:i,/%&C(7Q4v&d#__#n0i]*p/K(+}%}8.,_1N!<$kk(S-{ +Dskf,Iw/$'6/+y&z-fj&y dk#2a&f B,f[%nin;(6UZX%QMaQ';p{z, (J:,Wq|@*,9,b-iM4k+ NG;-xeI/!e'4;#a:S~&E5g}'1Kz(-t%2B%$B0Q *W^X)FuE('e5+_'ku$<)g1#<-?5Gf$t@V)+&0<,,'-Y[+fR`_ %P3C*RU4k*PwmR $J ^(AkaK+9_Bj(gA:F)}P-[,};u` ZD{?)IMZ7%YPpW'/k$u'O(wi+h(yw#Jf}m-S*.A'G9me%TaM$%jBPd-($uj+BPPm#zNCT+@R*$$#=+D'i3Q<%[t+3 :8f.'?(NF*e:iA*JT=m--$5k&g`cT&Rav%%4Q*9&:N1c%'&qe+>K^|!e2DP(#Dj{(b.&t+sp/a { {f$-Q/g'*&uY$H0ai(Z.Jr#pc~M!0>a5 ?Q*+!aYLX'%'l:$/0o4%]8ug+C&kL'fkpP hEPL#UhXI!WsS1)?bHI)UBk%)T1{X idm(-~R}r#K]S;#xD8Z->hXj(>F$f(V&9Y*&*Jc&6;'C$346-'.$bP$Afo/!5W;8()(d)(<#rO)oujX+J74[ v%;9'9{@J+PpUx*L!(:!Ym~7,8A4&.3I!h$u;Ly#|A@H!jFGP)UE#w'N#4F#lCd*)duuH(i9qV$>#6w!V1t,'jROK M.@q%0`*.#Jno((xCqt%B~jP&H!['$,.!|,!>c -%'3O $Rn;*&>lH&99~T((sGa-2XI^&}U}h&#!5D*=M[?.,!OU+3a}J-1;[}!S*.&**333#0ZT*);NBc'mCfF)SD_~'l#Jg(Jbd$ ~uF|%&(6V(~$-z,3m*R)q9Wd$up,<.7p}=*@o.>)<Z9U#l7.L#[;$w'o@We&~caU){`y@!]))* Fy<#(Vn8D+W*y8-{ln}*>a_u)zc(%$U8Lg%(n=r#Mz`E#D[Q;-0|ex,K0cF) $Q+!%,mI)+#R'#%|_T Q/PZ!HOJk(WP;5+R]{m,/79V'6z0d)Rfi[*HJP@.&;^?,GrWK-- ?f%lhZ,!C!Qh#5gDP#PS6G%k@ B*y=?Y#m@)S*XM~S%~N<z'u0Rn%Y*q($6%0[$oEY}(_-ZU,7]Wr /a?o+&]-o!vEh.$u8MS#(aj>&.a+~!Z4'D*d`;8)=!e&%LTWD%:6=H#,O;&(N.Ig!>d?=!Nzn7'@cou'u[25'Z^nP&r!!7 q#.b%_ZkH c// .#oFi-b)w&%7llK!6@Cu)`e?^ ~Ok[%&o;e(>yiM%Rb4+$[,^#.7A@!)f^b_!YG6m nX'Z'd$vn$bjd#!GYCy%V|2**(I^Q&&5xG$SBos ]c@j'k>T#'&m2m#,J**'r+W)%D$!G%bub 'J<.I!GhU<'B&g],,f4D 6Xt`&f[lY-<3i##dF0,(U6>a,O<k6(3o(h,*o)=*6H=B,*>#W-D-UG cPC#-8w:3&U_eI+&jr<+e&M%!sHy0!dg>$,X79q Q.4b 8CXl)bZ_2'R(L_(EFo9./&/J-*1Y!*9zZ7$egGT*zT)*%Z?n]%133/&q*cY&L5:>!CA_R$MvPM,{<n~,Nv+/-Z)ZU%iaw1&!,%J$w~LJ-@c)$!hB]J&+<3()xY/|%Eaby')sZ>('L+f(W~;V-Ax@E#:}6u v5Dr#5R?I$I.L$+JQX:-mD>X'Hm6Y''vID(opM+.&Obu+&YH !q7U&!GSi_+bfe}(Ub1~,pCfR-f.=Y'(xrz$t&uv&& (_* *~K)|w|&*{&1_-^&II$o0A='T~tw!s3hU+@QX} 3+Cb J=;4$<O m Gy)6&1+<4%?TGV)Wv_a+.eR-)=Vr%$OZ&Z&Q^d+)sr~X)!ZFL-O~^6.W4yl-<#M&)],t{ 'h3s(k_>1.(EHS-Q4_j!V,Nz&u1TZ*Ty_z#bI#(.sY<R*w-G7%m}AE-v`D9'/W4/%Mx%..z[hg v7 ,)+,$P QV%',$sym A9Qs$|Un9*5'@Y,+bso)-)L=$]0YW)iS8b*AWdk,+9Ax( W7&%?)Ys)}x0{-_o.!.i<xm,|V%z!rjwW'2R[{$jo}S&ZsJF&#xL2%2)ey!|Q/A%79`=(&4oI(dTRz$86ua &k/h(V#s)$R0~R&=;c'+0cJ;!T4K6 !VF~!.7/.(=:y$,Qvt5#~p1!.'0J*'9Te?-(rmM%e~-_*L=MQ*$K]g#t'U2!@-$(.LE%F)6+a8*&~*B(x)rB ju~u('PZH'xzKd(An47-Dop/+Lm,N*3kvV+;&zn+[N}b-bMqq+=Rh]$d&gk!V.qh I~wS+f=!n$A9,h)PE@9 VLO>!,zT/.K0;%,pH$Y#*cg&$)(=`!)/~<)DYs>#b%kU!f68Z#,*Hj(>!s?)g3,})JPt$.p'#Q,1Fd:&!'%o%YKjZ%=xc0(zM9;(wD8Z!c|%w*bdN(,(U*/#is:;*YaB'.VgOf&+^}{)m-_q%pLSe&{AFG'{N{',csy{,c(P..(`AW'>1ci&x'Z.+n<U?,c!<|$]TtA OY]w-[h(}#+JoE&^H2L+WrJ%']/M^$,rz,,i0e^+!/#V,4qy:#3Rv6 PFz_%]W-4 f>2J ZUPE'dr~/+l]XW&<!EO#=o?8'RG@* (D.Z(l '!,ZEfS%C;o^!!@F!'@:t)#M)$~,1;lc$yzI[':dp~*_~gT*|R0f$#m&>*>)Fo V_*_([!#%&NxEB%YNm&)BP-j&71Hd!{,/v!2TG} 3T81#$qy`!ZnR($%yWt+o#3I'xdh9'XD6U(f;L>)@xi%&DDuO);9V]&]Bbh,'`vE!|*B'*ORWh(xo7X*cS(i&|/3/#_@3w#SV%**w#Zm!gu1~)<|-p+DcM5,DG]n(3.zT$X&9; yV?)+Y0'S$!ged#,tIt+nO?I+t05u'h:Ii)r~w>'1imC-7$f-%5.9~%C^}9'm~0!'o%7m (eLG Ns;w!.4e}&rBZ6&Dgh6+R0O2%Kl.R'.+M=+sOqF+zn%9,XvMS,?pyt!'|D(+7tpV$Gg*L+xmu_ xeqL)4~&).KS9F$'|2#+.4_;)L~-q-|w*<)+j;6*!,c')=jQ#'uH|w)5QH>.v4X/!`M$B+Ye9-,rTMf'!NoG$*+X]+G~mF*|$/_#p-Hl&&I6A%}*f:(a.;9&|:x+&-<=3,?THR UKF!+(@i!+HR#Z$*tkA%bRM%'4Lda+V'ca+0Eq=)-Us4.sL!P$$rwd!k'<.,9hAD$wR*C(qjp%.~H+^$74R,)3v?d*GpdV tNW| H5v4 DQ0c)NAQ})1)l$.a!6b*/)hY!@T V'4?&e#2C]`*0vqf&NUaU,rC$N'BS^R (@Bq$JNsw%t9 + 2g54+@q>)%paqL,)Nr;,Z51B#Ctn-&L.K* ha W(,3C5&TkI<$Dv|<#a,p& On]D%2Y=8.'Ahf,`K~'-OFn&+89w1,Vs:&,;-he-#:_r-jcLn((fL'$s3&u+ty9K%(9a<*gj6T*H6hw-)Z_) 79tB#uF9Y+wuh8(7F5<'xU)--wDkQ!VN`S-Wduo MnDo#pCzu%`CCt+oN<A j*96)vsN*!@}Z,!fj-L&@a@d+4P N$o6yT*jEef+hML@&x+w@-[eAg, l5v+E1Wd*A3El%c'4R-_G`S-Y<@.$oPO;,5|8V tF2! (`q/(6+!;$~#In$qP }-Yp+j a#t%,^qWK&.P|#%&01C%w/OL* q + Ff)V+gG3'%i8Gm*bv?z B_GI GKcK A=?& M'LB!oFSM#O`K9,/UJ1&]x[2!YXlU+;hSs mb&~*Pw X+kyAl-srfd&qz>q'F,i[,R1>D%1syz'b|jT'W>7i(]e,r+YL5u#?pB[$%T2+ c]T)*7~a&*b>Ui#+*0),<NfY%hs>X)0V0_%*ZnQ(dG=H)){ze)Au*%&TwZw-fgD.%]C<i$`-B(&j9Np&dWLP'V0wR!]{3K(k*f3.}sTc(R%%0)ag4I).pc> $z+;$;h}b#~kFB(Cu@+*6ywl,.O~j$t0%h#5Lo~$Wa9{,FV2~((&|_*lP8e!dR<|,cBdn fH~t(".toCharArray());
	
	static void solve()
	{
		for(int T = ni();T >= 1;T--){
			char[] C = ns().toCharArray();
			char[] P = ns().toCharArray();
			if(P.length >= 11){
				out.println(0);
				continue;
			}
			long pl = Long.parseLong(new String(P));
			
			if(pl >= mod){
				out.println(0);
				continue;
			}
			
			long cl = 0;
			if(C.length >= 12){
				for(char x : C)cl = (cl*10+x-'0')%mod;
			}else{
				cl = Long.parseLong(new String(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)
	{
		long mul = fs[n/INTERVAL];
		int base = n/INTERVAL*INTERVAL;
		for(int i = base+1;i <= n;i++){
			mul = mul * i % mod;
		}
		return mul;
	}
	
	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