#11727 (C++11) No.148 試験監督（3）

提出ソース

結果

問題	No.148 試験監督（3）
ユーザー	LayCurse
提出日時	2015-02-09 22:50:59
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	101 ms / 1,000 ms
コード長	9,151 bytes
コンパイル時間	1,584 ms
コンパイル使用メモリ	146,908 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-05 21:29:02
合計ジャッジ時間	2,944 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	26 ms 4,380 KB
testcase_01	AC	35 ms 4,380 KB
testcase_02	AC	85 ms 4,376 KB
testcase_03	AC	96 ms 4,376 KB
testcase_04	AC	101 ms 4,376 KB
testcase_05	AC	77 ms 4,376 KB
testcase_06	AC	57 ms 4,376 KB
testcase_07	AC	92 ms 4,380 KB
testcase_08	AC	78 ms 4,380 KB
testcase_09	AC	5 ms 4,380 KB
testcase_10	AC	5 ms 4,376 KB
testcase_11	AC	2 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[77000000]; void *mem = memarr;
#define MD 1000000007

int get_inv(ll a, int md){ll t=a,s=md,u=1,v=0,e;while(s){e=t/s;t-=e*s;u-=e*v;swap(t,s);swap(u,v);}if(u<0)u+=md;return u;}

const char *fact_str = "Q%'*86Q$G')Mj#/L-l#-IC&s&C;.1_#:>DDz%2(%Ek#,(8$S&DLF3Y%05F#[@%%C_75>@^&:42;]G3'=t$KD$4o#?$<J^#+;:)s%#L61c#4985k$3A57c#*F<&o$D2:/z#+(<&h+MMY$HMO1q%&>@#P&.LF,g&1<HU&'ME?Z3%C?k#/J>Cv&&'+(e&/M9@X$240Hw$-=5:|$?9@BQ&2=B6h%J61KV49N.]%9@.,uDN(IP%9-<#P#6FBF{#<.>-nH=<7f#M$'8w$<7$7y#5F9&r%MDF,Z1#KKt$5&M.WMJ,M`%9.)E`#&OJ1V#O$F,l%B/8!b%>CA@n%M.GBl%ELJ5T(')OY$'KAN{/.NAk#13<U%C'@?]$M5)Cs51FDz&0C#'Y#@(C7z#FL-.}%#B?K{%H*B'i%L;36g&H@3Ei$HB;-U3)$m#DFJFz$13$Et$JL0Kw&$O6.eN?=7R$;@-As$G7<(cB7H6n$,;;@`$=3+3e$(+?Gi&%AOCh&2I&Nw#(A)JW&01;Bh%*:D%T%<9&$v$(7B'Z5+64r&/979_.<7-s&C5,'}GC(:V%KD0Kd&9,DHo&-BG6t&:EO;z%/%*.S$DB#>j;%+JU,#=:S*FN8[,<O4^:/NNu#2MEBg/6(G{%2ALGT$&@+%}%*-=m%D&!!a#M49At%3A64r$$+G$s#%)1&c%+A,*Q#.7?N~G<%8o%K)B.Y$?9;/X&:HC?j$H59._##/?6P%?EL3a&C*3Fw%#-ONw#>I1/Z#*11E`$AK0Nw/4M.u%J*HKp#L5.9uH97ITE?,$s&0+%Bc&B@$1r#+L5*~$2O;1z&),M4z419LW#'J&<T$8@)/p#*9K=`2#'h%3/E4e#.338p&'>7$[#<*=At%>O.6`$)*6Hz%+,@C}4#4&k$E02*i%,9K't&!EL?XMD9(b$FGI&^$,.(DT%;3CIv##;@;[$7B/@`&!GM*Z%/8I+g%/2=4[#4BGI^0H+OP$B)JFxM>2-V7AM>v#B%*4i%G2!;f4?D.v0F=Eb-?MAb#8@#Fp$@0;.}AMG>Y#B)N1y&6K'Gw#6)EH~&H7I4r'(6Dy$L8*Hw%?*:G]KHE#U::6<x$F+?FX9<?6h#7LO2s$?(ELt)BHAw#<C8;r$'F.*k%$HG+W'OJEr&:5J2n$O@36V#)3':b$8+A#y$B7;$z&5;5?j&'=J't&@*4&P&8>C4x&6,H>w%9I-K~%&,78h#)*#8g&=12$X&50$A];A1$`$3M&0^$*=(6z&$7&D^%B5!(i#F4,?_$0.2)a%=4?=u,$M*g%L#%He$-CA;}H6-Mx2GA?};N6,n$C?(Jg#0#N8sHG4Nh#*4L3s/D;:m$1<6*t&;;83q7-J3u61=Jb;EM;s$4;B8f@38Ct$7'=-Z%6CG=R;2F#k#EH'@Q$D()+b#0229a#1K#0y3H=Aa%4N58n;&@Fr%;'/Ox9!E?X%/5#8g#?G;9TG2*(^:*E,g&%46>j$1$:;}#0B.As@.$Oo#2#*8l$J!-<b%M.9>v#BL&Ar&0?:0P&%<2)eLN&3[%<6)<`#:@OK]#$<O2|%H##=l%!,3*WJJ+2W#I$GB[&H7=Cp&2A7Gx#>K0Bm.%5=i$N9G1W$#@4Lk&A>:/hEGJLaCF>!Z&G04*Z$MC?4t$*@:IfHDJMc%(M:BQ&BI'1m$5HIEo%F,D'p*C+Ea#1HC3x$,GCBw%)5!.V$-$63m#D'*2`%'D;'|$C%1*S%-,&2f%12IEv%.4N<b&?J5I|N?2Ar$CH:1T&&!3N{#J$E*z$6EH+q&?%C>Q>B#Ix%1(D3t#6G=El%82-Bb$G$!!~#;,G6]%DAA;v#8:/NPO?86|$F&KEm(L-8T$*=-;R#E''Aa#-B95w$/>F9p6O''j$I(L7v%E3&=e%I)G6i#5)*.i$:=33S$G:AHn#>KN1~AL<Iz$/50+P$C$C1t#>*/C_$5:69s$-E(GZFF>/Q#9#)Mj5,D%g$G<HMl$CL'7i&?-CAp%#8BK{&2#,&a&03O?T&$K)4u&8GG=Y#J+L@qK*@HQ%9D.(j#N%KO]%7D,7P%8(&B{&#8OJe#I>G9~1.G=r#9*6rL.*8P1-L9i&<DFL^#N>=HZ%M(:HXJ&04Z&!/)5t#@F)Jp&F!6Mq&+O-/jC)M&~EJGDQ&/!L8f$J+)6e%4@6(b$<0-1[#787G}&CCA8s#)I$Ji%J4LMr&<%&>S$=9@|#<@3;q#A/?8^;DA>e$/FHDd#$BO@~&.+(IXJ+//g%4.KAi&6GH@e&)3'!W$',5.X%L=H3U$$)?'m9;$+_/3,'Q#<#(.U3FO&`%7DMNh$%J.-q#LKC>]#:A83T#IME(z&<!D1~&;2?Lq&<$@5k&=>H/q&$)?7~$J;A>w&H8/&[&F92Gg%3G$/x%&%JNj#1,N4w$#7L8P&8@CL~&>G&@l&1=LLW/'EY#D&BJzAA8JQ$GM;1b&F<.=`#A96HS%E)-;p=OI-v&>9H7v#+04Bl#@>0Cp$DM85l&HED5g#!CBEa#HNM!{C4G.|#KCK;u#9#MHc&G.N9m#.D:0v#<@A!U%F,,0Z$A%&/c&G/60X&G&3JnDD.E^$K.B.P%6L.IZ#0$#.`$*G.5Z#HCJ:_$-1!K_&@G2Ng%*+.Kh#I8:.R+1=Ck&&2#%w%.G45S&&I.)Y&:@:!Y%=9NOS#162'W%,FGDv#<F0CR$;905{#,4?/|$&8;4f$AM$0l%NB-LW%@8&?v%I=:ET&5$M?r#2-1&[%8B=Er%$3)Dd$$L+E~#;HK1c-/D;q&#H5@PN4%Mk%4F*.c8)(>_%6!0Nr%>L>Nw#76ICl$5$$+P#'47z%:2MEn#I6K+f#6)2K^K%+EY%5&8@u$A06H`%;A.'Q#B*E5b'G6'z&*FE3}#$3N'k$C7++t#BH$FZ%G(!6z%;F#IU$62DDZ$,B?Md%K3B)[%BK4tJ48Ay11O7p&F'AFP#N.A?w%?66)c7I%:S$N>M6j(MH?Y%,!FOc&+#GIh&+)4.jG8-/t$BK+(R%87?-Y64:*`$MNILv$/C2.a#J%27wD!1Km%0.)3x,7!-R#9M#/l.>MOW$(K(6y%IL*JR#-+:%~CMK$|%&*!:c#J%-=b$A9B$g$3D?KU&7012Z&H7&KP#<N.BVEE1<YAA&6z$>F+&Y%2HG,q$J?M2_K@H'k%1H>7y$D/1!_%?2#AW$:!'NP$A%FA}%3<M@}%E&2Lz#FFF3UFA5%d&65(Kh$,)K8R&8)%(e&5E4&}%ECL2e$-@+5x%&7OKf&?B6Bw$3=$E_$+**3m$-/J5l$6*6?y%J5=I|868=y%4/+*R&'H34v%M-J6U$(#@An$M:G!^&4C?/eJ!(3R,CA7w$775NV%M1@Dz%@%79i#M?A$~&'==(l%BBJCd)CE9X$<155d$'21LW'G,Fe#!8GDW$)BN@_#!%EEb#ED9Be?5F.qK7.HV%(J@7T$/<O3{$:N/Cb#0<+>Y'=6=m&)LK-f%NA(Jd#=I>Fv%9FL:d$'CGE[%4@9:s%#N(=Y#2G.Dj$8$.2V$K0J5Q#6$+1~#7ABF}$-IODP#0LG7z$>1)N^,K>$X&>7)!Y&;L(.e$D!/KV,H;6tNN)Nc$2+*'p&*744c#<HI;tJ;?HW%-/)Hr#3M%OR&A@I-v+I6$i#D4'Ew&;&:9v#O&O>^#/A$Bu$+J2Go$,:GJ_=J+'h#.=!Lv&7:31f%N6J<n$2%AGmCKK>mG0=H_$384)U&3EM,_#DDFJU#F+K.W#?FC%o#JGA)c#$BE-V#+?C0|&5'8Ke#<'7.iO-N0P6=G&_$EO=/n%7N?Q7%('S%>+-9eMI*Aq#>@E(~$&CLd7N5$k&/!?Ay%CL?9Q#'G3=s&02:Ea@CB#d$H'C@a#O!BJi&71H+d&5',Nn&F3(2s#90'$s#G7D)e#.J>3^#-2H;T&-C@,[%4N=&wBHDAt#8H+GZI+%7bJ.I>h%J)B)P$M41CU#IJC/Y#1(#Fk$HNMDx%02=?e%,I2%b&=7GC~%NM1)x$6++5Y#.948Y&!6DAP>1O:|%4A$?`#:/9Oo#@11CX$C/@2j%N'G@h,66DP,O1;PL!!JS&?M<-a07J=T&:7,4V#=@??P#?9DA~%BK=,[&,,01_&D6K(s%%/53b&CG<Fn$'2)HZ#3!(!x>MA@U%A1O(U&!IE4oNN8Iu&7(9N{#;M'/s$@20I]&F'+#j&(20*l$J7,1f%1L9O]$B(;=p$D?:+x$.MK.m##:A4v<0@NQ#N.&JvD?F7q%,(>7d#!>D6~#!%/(l%81N!c$3*J.Q$!9D!k#2AH,}&A!*%o$=1!JU##L5,u#GGAKZ%M(97Z&8!,(P#4A+0x#%'9A]##,DGm%4<3+P#M$N8w&*D,.p(%GBh#$=:Lr#GI8>}%M#2;rIJJ$R#+2.Ij%/&53Z%M5(NP&*DJ=c&)7#Dg;624p%#40(_%:)>>S$D(I=x&!;)4V$0NL#Y$((3<x$+4@/W%%6-AX,HL0~%K(:6f%.#+&^&=&D(i$7?<Dc#M$N-u&23)>q%'HEFR&1-I9U&#'ABY#2#)%Q%71D5`%#7L<W$IF81y%L>-;a$8J3'u&1M$E[%7D4KV%$64+w$2+:!X&74K,~$8>5-f%?)N2~#N)!'p$F/F#a3,1LxH6$Jf%O&3M{$GI0?W%8H6w%6'MV&-<%-jO3:5X#/&-#m&.AM>r&4D7,]&F2!:f#?M2Fp#/'1/_#F=;#h%G9'-o&&%'2l$$A;,s%,++Bd%3<K&m$4M#OqF)LDU#>'M0o$>I0*Y&>9@<w&%NL2RF12Bc%$@,:YL:$Ob#0+8Bp&#N=NT3(BH}#@*(Oj$$,L/n$432C}%?CN-u#:G;*}%..@0U2*@?c$4.!5z@/3&u83C)d%0LK/s%&I>8e&442:f&9A5Of#2$)Fl%MJ9<z$C@%(e#NA2F}&/ED']$-4Ei/:HEX&EB>(r/9CMy$A%5Aa%KE=L|%OOLNq%:7-?P&=3,Le%/70Jh&&&:FdI,7'b&1C,6}$>/9;f&/CM'}&=3AAY<$=Jr%?736r#)L24`&,;=6[#2M*)dF>(Ir$CL.:x%&OK2o%E!./_/-@Dv#-.L>r%.;?K[&7,&0n#<$?%~%@/2Nc#KK.Jx#8#H#}%C3D;cF#F/R%@<6B_%$*1={%//20]%J9?N^&'&,6}%N4:?X%18D@o%GF;A]#D'E!p%4>'>`$MC7Nb#*K,8s$L(?,x$1>?|%:C>Gw%A=JCj*&I2y$3E*-S'#D!d;</:|%(?;3d$HNN.r$1B:7|%88L/[%B:'!|0IAF[&>O1I_#B8L9o#8K)Ky$42L,x%%A+KiH6-7X&+/.;|#E3:;S&7HC7b&AA(.w#.)N!~<,OA[&@NHO{#(N&CR%!=)!ZM.I.X##=-,_9LD&^$L>3LZ%I**Hk%@J8Mk#(G.0r#E$>*Z%)9%]%@*:3]%EO#E~'FJ;|-#4Hl%3N+5w&)O?IP,MC;v%7/F:X%<A':u&8,$$y%KDK/W4C?>k%09>Kz#$:6I~&/.:=aI:&<d+G.~9:5=X#K&M1z$1)7X%5D@6n#:3.Dl$DD$(t%6*)J^,DF+e&=06@W#A8>>^#2H/6e$-389f)#@,XK5((k&AB*-Z&GB-5U&6?B)|&.J%A{&2OE7~#;K'%p$88?HU#7D4H`=#':V&B#<J~$4$.A`COOIzFM+,g%/K5BX&6G42h$<NG=Y%=?--{$4J/Ev$=K1Bb?1FKy#H.;Hz#7.4;q&*$:3^%/&.*{#G4C8Y&'065}%OL1Du$FC5Fd218(P&?.MHa&'/7(X#)JLOf%(5:2i#$-=8cOOJ;tC8)j%F4;0]%OA80p$K>*>e&,+5Mv%4#08XPPPP";
template<class T> int extend(const char arr[], T res[]){int i,j,s=1,z=0;static int c[128],f=0;if(f==0)REP(i,33,127)if(i!=34&&i!=92)c[i]=f++;if(arr[0]<' ')return 0;res[0]=0;for(i=0;;i++){if(arr[i]<' ')break;if(c[arr[i]]<46)res[z]=res[z]*46+c[arr[i]];else{res[z]=res[z]*46+c[arr[i]]-46;if(s==-1)res[z]*=-1,s=1;res[++z]=0;}}return z;}

ll fact_memo[1100];
ll get_fact(int n){int i;ll f;f=fact_memo[n/1000000];i=n/1000000*1000000;while(i<n)f=f*(++i)%MD;return f;}

int T;
ll C, P, CC;
char buf[200000];

int main(){
  int i, j, k;
  ll res;

  extend(fact_str, fact_memo);

  reader(&T);
  while(T--){
    C = P = CC = 0;
    
    k = reader(buf);
    rep(i,k){
      C = (C*10+buf[i]-'0') % MD;
      CC = CC*10+buf[i]-'0';
    }
    if(k>15) CC = 1000000000000000000LL;
    
    k = reader(buf);
    rep(i,k) P = P*10 + (buf[i]-'0');
    if(P >= MD || k >= 12){ writerLn(0); continue; }
    if(P > (CC+1)/2){ writerLn(0); continue; }
    
    C = (C+1-P+MD) % MD;
    if(C < P){ writerLn(0); continue; }
    
    res = get_fact(C) * get_inv(get_fact(C-P), MD) % MD;
    writerLn(res);
  }

  return 0;
}

yukicoder

結果

テストケース

ソースコード