QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #38326 | #1176. Binomial | wyhao | AC ✓ | 2732ms | 103204kb | C++ | 760b | 2022-07-05 10:50:17 | 2022-07-05 10:50:18 |
Judging History
answer
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
typedef long long ll;
int T,n,a[N],s[N][25];
int ma,w;
int main(){
scanf("%d",&T);
while(T--){
memset(s,0,sizeof s);
scanf("%d",&n);
ma=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>ma) ma=a[i];
s[a[i]][0]++;
}
ll ans=0;w=0;
for(int i=ma;i;i>>=1) w++;
for(int i=1;i<=ma;i++){
for(int j=1;j<=w;j++){
if((i>>(j-1))&1) s[i][j]=s[i][j-1]+s[i-(1<<(j-1))][j-1];
else s[i][j]=s[i][j-1];
}
}
for(int i=1;i<=ma;i++){
ans+=1ll*s[i][w]*s[i][0];
}
printf("%lld\n",ans);
// for(int i=1;i<=ma;i++){
// for(int j=0;j<=w;j++){
// printf("%4d",s[i][j]);
// }
// puts("");
// }
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 27ms
memory: 99304kb
input:
2 3 1 5 6 3 1 1 1
output:
4 9
result:
ok 2 number(s): "4 9"
Test #2:
score: 0
Accepted
time: 813ms
memory: 99312kb
input:
10 1 1 3321 108907 496886 513637 107549 602502 235745 583320 401703 649106 841450 806050 127630 250786 780434 780387 256680 723365 604626 255396 251497 992405 594166 951810 524404 585892 85571 821715 581042 711296 187617 367585 862536 856196 312147 121285 967957 495031 855565 619680 318939 618420 91...
output:
1 38911 1158 22249 2006 3213 15043 426 88 1191
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 2732ms
memory: 103204kb
input:
10 1000000 319659 282355 805517 492423 78447 187157 262446 533612 55339 671293 251238 188866 598658 986 776564 371192 215026 344057 213583 577027 674883 552835 500207 727954 489932 483338 232733 115534 570113 151973 327011 625780 642233 103699 19128 835797 38112 153973 826458 967214 835438 460333 55...
output:
2878293352 2895860805 2882764772 2873109297 899786118 2881907624 2877368557 2878876021 2886310256 1000000000000
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 1535ms
memory: 103200kb
input:
10 1000000 718932 525438 143858 344614 550176 446529 196655 638381 759927 201969 993978 241046 764752 912950 618918 311293 125072 501708 425676 818137 48751 850412 17011 377597 877339 595417 993334 770612 588927 392617 877160 132425 313060 791691 452471 128719 115560 788866 333356 871641 805214 9461...
output:
2878293352 1000000000000 1000000000000 1000000000000 1000000000000 415869837 1000000000000 1000000000000 1000000000000 1000000000000
result:
ok 10 numbers