結果

問題 No.148 試験監督（3）
ユーザー uwiuwi
提出日時 2015-02-12 17:52:09
言語 Java21
(openjdk 21)
結果
AC  
実行時間 780 ms / 1,000 ms
コード長 3,568 bytes
コンパイル時間 3,700 ms
コンパイル使用メモリ 79,776 KB
実行使用メモリ 58,108 KB
最終ジャッジ日時 2024-06-23 19:09:00
合計ジャッジ時間 10,525 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 262 ms
54,208 KB
testcase_01 AC 312 ms
54,392 KB
testcase_02 AC 542 ms
54,252 KB
testcase_03 AC 606 ms
54,440 KB
testcase_04 AC 756 ms
54,056 KB
testcase_05 AC 504 ms
54,276 KB
testcase_06 AC 601 ms
57,644 KB
testcase_07 AC 780 ms
58,108 KB
testcase_08 AC 699 ms
58,048 KB
testcase_09 AC 265 ms
54,600 KB
testcase_10 AC 272 ms
54,804 KB
testcase_11 AC 124 ms
53,840 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class X {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
	
	static int I = 3400000;
	static int M = 1000000007;
	
	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 = "!    CLc!-|k$k-d{e$#OZL0 @x7?$`e4/&1j50)i?(C,'?jW-<0FN'#*7}$5sMq HFc%#ZWcR!9ZM^'c{u|'5.ev*['x]&S^>Z'dhrT%1{-k%2KLX gZ=E-Np6e u*O.({>=H&U3#T'`'Fa!.J=2*^M2O-vQ+]-VT.,&!2($&4kSc$T#^y#PB}j*]r-l*]DSa$M 'W*4/2<&r[;*)ii|n(c'BS*RBRj(E/Q~*o]8--3)>X)VRm=&Fo39)CaTt *<S6)Lrg5 !L&I*w;8A*0QX%)(9A&.|Gkv- =h7)VJTx)aDqJ(>^/h(TC%(';3iS)4|of'+XSB'QK.%+>O4}*@@ Q-#>b#&-`PS!dhn@'E e)-f>GA Lrlo-VEw6#c|G1$gOrx%@O;s NF2>%$8I:)=)jz*Eus<-!WtU!_vvC$K-*}- (u>!6^]K%S;H{*7wa+.E.T8,9kR=*yh6K #|^/,^Q54+=u5K$?DRO#GRE!) Sn]%CR'+%wJ6-%^o{u%)o2L%Bw&;+o<fD,`O],&(h%q&juPO'T>fo&2D0h&:D&D*&<u,*lFw*#tNo& AJNq(t@:K,b_)|+}.Yn+CJT_(4(V(''C<.,HxS% Sj5y*TKPD$`{tw$F(tB+W@9`-zC^_*h=4v'Dk#_-9Zn7.G+6U!:<os&nin;(tR<~-=pCv*YW@1%Cpff  u,/+P~/Z)};u` z8^y-mWHS-( L7+hp`D'X+8a%-0l.-{ {f$^_JK#%ub6+y.[=!%6Y_(E5~w+3DPu-<#rO)H)=h }01X$=}mN%k[{'-jhxy';#{N#2XI^&j$.^+qYs0+w2}:&o&Xk-D^Fy%[/yx&>a_u)!V^ %x'X&+PU17$+**t(R?lT#Y<dz!6%0[$a}P$#*sdV,s<-|'`a]!(Y,c^ Hsp< Rb4+$UW+x*=ty#$_y1V$l5P%+4:AH(PD+a(D-UG 02h?$eT@O!v:)T(^,B{&H|PL+!i'p!xY/|%7 Rr)K&7$(KTUv'lrb*),|~c){Nx>-3+Cb ,h*p,6 .[ pZYP%J>Qn,`%'Q&ubw%$QV%',7tJi!:U5$+QZB9!?/Na%)%Sk#_G G !VF~!$yya)#=b{,-]vR,IX0R-~tUH,z@jK,VLO>!9y;s&>y ?'./PR+Buxe)lf6l+/4Em+(`AW'^$2t!^Y%c&ry3d,DyZc,puBB)8Q>z yzI['*^` ,OTf6(m*cj,E}{r'-KS;#@zt|,w#Zm!Z;9I#1h[F!#(*@$mf7A)e96!,dvk#'7tpV$-1Eu)dW&G%tk~T)H0xD**wMc-([@%&bRM%'|6Aw+tM{8)SR_0+<o-q+/&&Z-PETJ'paqL,jhH|+p.U[)1&vc,Wyk0$_=6g#Nydk)Wduo q'<b(=}z^ *O{% dxdr#[ffc-WOB;!w/OL*d5=@!Us4g%mCrl 3p**&+hTx-)QH%%<NfY%K*U0&u*#8+[pk ,8dhh#s-q6)l,[2#fH~t(".toCharArray();
	static void solve()
	{
		for(int T = ni();T >= 1;T--){
			String C = in.next(), P = in.next();
			if(P.length() >= 11){
				out.println(0);
				continue;
			}
			long pl = Long.parseLong(P);
			
			if(pl >= M){
				out.println(0);
				continue;
			}
			
			long cl = 0;
			if(C.length() >= 12){
				for(char x : C.toCharArray())cl = (cl*10+x-'0')%M;
			}else{
				cl = Long.parseLong(C);
				if(cl-(2*pl-1)+1 <= 0){
					out.println(0);
					continue;
				}
			}
			
			long sup = (cl-(pl-1)+M)%M;
			long inf = (cl-(2*pl-1)+M+M)%M;
			if(sup < inf){
				out.println(0);
				continue;
			}
			
			out.println(f((int)sup)*invl(f((int)inf), M)%M);
		}
	}
	
	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%I;
		if(h < I/2){
			long mul = d(enigma, n/I*5);
			int base = n/I*I;
			for(int i = base+1;i <= n;i++){
				mul = mul * i % M;
			}
			return mul;
		}else{
			long mul = 1;
			int base = n/I*I+I;
			for(int i = base;i > n;i--){
				mul = mul * i % M;
			}
			return invl(mul,M)*d(enigma, n/I*5+5)%M;
		}
	}
	
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static long nl() { return Long.parseLong(in.next()); }
	static double nd() { return Double.parseDouble(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
0