結果
問題 | No.766 金魚すくい |
ユーザー | tails |
提出日時 | 2023-07-13 20:18:25 |
言語 | C90 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 4 ms / 1,500 ms |
コード長 | 2,825 bytes |
コンパイル時間 | 637 ms |
コンパイル使用メモリ | 27,500 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 06:23:33 |
合計ジャッジ時間 | 2,623 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 0 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 0 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 0 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 0 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 0 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 0 ms
5,376 KB |
testcase_22 | AC | 1 ms
5,376 KB |
testcase_23 | AC | 4 ms
5,376 KB |
testcase_24 | AC | 4 ms
5,376 KB |
testcase_25 | AC | 4 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 4 ms
5,376 KB |
testcase_28 | AC | 4 ms
5,376 KB |
testcase_29 | AC | 3 ms
5,376 KB |
testcase_30 | AC | 4 ms
5,376 KB |
testcase_31 | AC | 4 ms
5,376 KB |
testcase_32 | AC | 4 ms
5,376 KB |
testcase_33 | AC | 4 ms
5,376 KB |
testcase_34 | AC | 4 ms
5,376 KB |
testcase_35 | AC | 0 ms
5,376 KB |
testcase_36 | AC | 0 ms
5,376 KB |
testcase_37 | AC | 4 ms
5,376 KB |
testcase_38 | AC | 3 ms
5,376 KB |
testcase_39 | AC | 4 ms
5,376 KB |
testcase_40 | AC | 4 ms
5,376 KB |
testcase_41 | AC | 4 ms
5,376 KB |
testcase_42 | AC | 3 ms
5,376 KB |
testcase_43 | AC | 0 ms
5,376 KB |
testcase_44 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
main.c: In function ‘main’: main.c:7:59: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration] 7 | #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);}) | ^~~~~ main.c:118:9: note: in expansion of macro ‘wt1’ 118 | wt1(r); | ^~~ main.c:119:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration] 119 | _exit(0); | ^~~~~ main.c:119:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]
ソースコード
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);}) #define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;}) #define wt(v) ({unsigned _z=v;do*--wp=_z%10+48;while(_z/=10);}) #define wt1(v) ({char wbuf[64],*wp=wbuf+sizeof wbuf;wt(v);write(1,wp,wbuf+sizeof wbuf-wp);}) #define rep(v,e) for(typeof(e) v=0;v<e;++v) #define MD 1000000007 typedef unsigned long ulong; void sort_aux(unsigned*a,unsigned*b,int n){ int c[256]; for(int i=0;i<256;++i){ c[i]=0; } for(int i=0;i<n;++i){ ++c[a[i]&255]; } int t=0; for(int i=256;i--;){ int u=c[i]; c[i]=t; t+=u; } for(int i=0;i<n;++i){ b[c[a[i]&255]++]=a[i]>>8|a[i]<<24; } } void sort(unsigned*a,int n){ static unsigned b[100000]; sort_aux(a,b,n); sort_aux(b,a,n); sort_aux(a,b,n); sort_aux(b,a,n); } unsigned v[100000]; ulong fac(ulong n){ static unsigned const fac8[]={ 1, 988636580, 695283030, 792464830, 211210084, 690746858, 350191551, 426484032, 41710039, 813460239, 558164830, 141497103, 950738028, 464835272, 97894695, 916372711, 110247743, 969786090, 503068962, 429662713, 960011178, 28831697, 64164502, 644858472, 580681420, 685687553, 732369763, 284072362, 973536426, 691577297, 138616501, 791335653, 857536770, 418934534, 59993985, 649008795, 469845601, 262024866, 82355309, 762601625, 779906992, 700811164, 768370249, 627482638, 120082832, 889761575, 393698932, 315006352, 501868614, 389081755, 110949981, 73117756, 246998080, 810960304, 899599758, 54240893, 285492803, 238086226, 756915097, 857420303, 590237245, 189189356, 27740096, 365659876, 182153956, 74775714, 449611889, 604699923, 708964844, 29899448, 434888300, 577073314, 913463884, 898026807, 117764246, 666808812, 948824387, 773943041, 562701063, 968037475, 324433771, 116780897, 718140143, 843054228, 916823404, 472625466, 934718736, 369384614, 632057771, 319626719, 855456001, 487389069, 688736405, 168349895, 918820931, 450077038, 715100901, 12311664, }; ulong z=fac8[n>>10]; for(;n&1023;--n){ z=z*n%MD; } return z; } ulong modpow(ulong a,ulong b){ ulong r=1; while(b){ if(b&1){ r=r*a%MD; } b>>=1; a=a*a%MD; } return r; } int inverse(int a){ int b=MD; int u=1; int v=0; while(b){ int q=a/b,t; t=b, b=a-q*b, a=t; t=v, v=u-q*v, u=t; } if(u<0){ u+=MD; } return u; } int main(){ rd_init(); long n=rd(); long m=rd(); ulong p=(ulong)rd()*570000004%MD; ulong q=MD+1-p; p=modpow(p,m); ulong r=0; rep(i,n){ unsigned vi=rd(); v[i]=vi; r+=vi; } sort(v,n); ulong s=r; ulong t=0; ulong u=1; ulong c=fac(m-1); ulong k=1; ulong l=c; rep(i,n){ t=(t*k+c*p%MD*u%MD*(s%MD))%MD; p=p*q%MD; u=u*k%MD; k=k*(i+1)%MD; c=c*(i+m)%MD; s-=v[i]; } r=(r+MD-t*inverse(u*l%MD)%MD)%MD; wt1(r); _exit(0); }