QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#136798 | #241. Chiaki Sequence Revisited | whsyhyyh# | 0 | 188ms | 23504kb | C++14 | 1.3kb | 2023-08-09 11:45:29 | 2023-08-09 11:45:30 |
Judging History
answer
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define LL long long
#define mod 1000000007
#define fi first
#define se second
#define PLL pair<LL,LL>
#define mkp make_pair
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define drep(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
LL rd() {
LL res=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
return res*f;
}
map<LL,PLL>mp;
PLL solve(LL n) {
if(n==0) return mkp(0,0);
if(n==1) return mkp(1,1);
if(mp.find(n)!=mp.end()) return mp[n];
LL tmp=1,cnt=0;
while(tmp*2<n) tmp*=2,cnt++;
if(tmp*2==n) {
PLL C=solve(n-1);
return mkp((C.fi+cnt+2)%mod,(C.se+n%mod*(cnt+2)%mod)%mod);
}
PLL A=solve(tmp-1),B=solve(n-tmp);
return mp[n]=mkp((A.fi+B.fi+cnt+1)%mod,(A.se+tmp%mod*B.fi%mod+tmp%mod*(cnt+1)%mod+B.se)%mod);
}
int T,n;
int main() {
T=rd();
while(T--) {
n=rd();
LL l=0,now=n-1;
drep(i,60,0) if((1ll<<(i+1))-1<=now) l+=1ll<<i,now-=1ll<<(i+1);
PLL tmp=solve(l);
printf("%lld\n",(1+tmp.se+(l+1)%mod*(n%mod-1-tmp.fi+mod)%mod)%mod);
}
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 188ms
memory: 23504kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
1 2 4 6 9 13 17 21 26 32 38 45 52 61 69 77 86 96 106 117 128 141 153 166 179 194 208 224 239 257 273 289 306 324 342 361 380 401 421 442 463 486 508 532 555 581 605 630 655 682 708 736 763 793 821 851 880 912 942 975 1006 1041 1073 1105 1138 1172 1206 1241 1276 1313 1349 1386 1423 1462 1500 1540 157...
result:
wrong answer 13th lines differ - expected: '53', found: '52'