QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #75838 | #5464. Dice Game | chenshi# | WA | 1ms | 1880kb | C++ | 919b | 2023-02-06 12:48:39 | 2023-02-06 12:48:41 |
Judging History
answer
#include<cstdio>
using namespace std;
const int MOD=998244353;
inline int qp(int b,int f){int res=1;for(;f;f>>=1,b=b*1ll*b%MOD) if(f&1) res=res*1ll*b%MOD;return res;}
int T,n,ans;long long v[31];
inline int calc(int n,int i){return ((n>>(i+1))<<i)+((n>>i)&1)*(n&((1<<i)-1));}
void dfs(int nw,int lim,long long sm){
if(sm+v[nw+1]<=0&&sm-v[nw+1]<=0) return;
if(sm+v[nw+1]>=0&&sm-v[nw+1]>=0){
ans=(ans+sm%MOD*(lim+1))%MOD;
for(int i=0,t;(1<<i)<=lim;++i)
t=calc(lim+1,i),ans=(ans+(v[i+1]-v[i])%MOD*(lim+1+MOD-t-t))%MOD;
return;
}
dfs(nw-1,((lim>>nw)&1)?(1<<nw)-1:lim,sm+v[nw+1]-v[nw]);
if((lim>>nw)&1) dfs(nw-1,lim^(1<<nw),sm+v[nw]-v[nw+1]);
}
int main(){
for(scanf("%d",&T);T--;printf("%d\n",ans)){
scanf("%d",&n);
for(int i=0;i<30;++i) v[i+1]=v[i]+calc(n,i)*(1ll<<i);
ans=n*(n-1ll)/2%MOD*n%MOD;
dfs(29,n-1,0);
ans=ans*1ll*qp(n,MOD-2)%MOD*qp(n,MOD-2)%MOD;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 1476kb
input:
4 1 2 3 4
output:
0 249561089 776412276 2
result:
ok 4 number(s): "0 249561089 776412276 2"
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 1880kb
input:
100 119 75 29 10 17 29 449 71 72 12 79 117 83 80 35 272 105 497 346 287 362 140 297 167 111 419 210 212 170 413 373 210 196 39 1 101 258 496 333 293 392 2 187 431 157 342 436 106 449 136 378 243 357 325 237 254 22 292 62 435 18 446 471 18 42 377 181 350 19 389 212 58 45 70 52 63 107 71 66 355 381 30...
output:
645006489 296012775 400009943 299473312 362683945 400009943 60548260 629323703 104754084 471393174 175624519 531171954 143020402 134763040 551682820 312599186 269095960 284396636 191400715 718400664 967774080 709364752 584864173 5941827 724073586 701650152 262576881 417830609 833275086 916357319 143...
result:
wrong answer 5th numbers differ - expected: '221064504', found: '362683945'