結果
問題 | No.148 試験監督(3) |
ユーザー | uwi |
提出日時 | 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 |
ソースコード
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)); } }