QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136798#241. Chiaki Sequence Revisitedwhsyhyyh#0 188ms23504kbC++141.3kb2023-08-09 11:45:292023-08-09 11:45:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 11:45:30]
  • 评测
  • 测评结果:0
  • 用时:188ms
  • 内存:23504kb
  • [2023-08-09 11:45:29]
  • 提交

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'