QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#346748#4770. Binomial coefficientsPetroTarnavskyiAC ✓838ms10152kbPython3837b2024-03-08 22:18:152024-03-08 22:18:16

Judging History

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

  • [2024-03-08 22:18:16]
  • 评测
  • 测评结果:AC
  • 用时:838ms
  • 内存:10152kb
  • [2024-03-08 22:18:15]
  • 提交

answer

N = 104

def C(n, k):
	if n < N:
		return 0
	ans = 1
	for i in range(n - k + 1, n + 1):
		ans *= i
	for i in range(1, k + 1):
		ans //= i
	return ans

p = [[1 for i in range(N)] for j in range(N)]

for i in range(1, N):
	for j in range(1, N):
		p[i][j] = p[i - 1][j] + p[i][j - 1]


t = int(input())
while t > 0:
	t -= 1
	m = int(input())
	ans = []
	for i in range(N):
		for j in range(N - i):
			if p[i][j] == m:
				ans.append([i + j, i]);
	for i in range(40):
		l = 0
		r = 10**15 + 1
		while (l + 1 < r):
			mid = (l + r) // 2
			if C(mid, i) <= m:
				l = mid
			else:
				r = mid
		if C(l, i) == m:
			ans.append([l, i])
			if 2 * i != l:
				ans.append([l, l - i])
	print(len(ans))
	ans = sorted(ans)
	for i in range(len(ans)):
		print(f'({ans[i][0]},{ans[i][1]})', end=" ")
	print()

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 28ms
memory: 10152kb

input:

2
2
15

output:

1
(2,1) 
4
(6,2) (6,4) (15,1) (15,14) 

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 838ms
memory: 10092kb

input:

100
2
3
4
5
6
7
8
9
10
15
120
3003
24310
495918532948104
1000000000000000
210
1540
2701
7140
11628
48620
614386
705432
817190
885115
4200651
4610166
5311735
5918520
6299475
6666891
6876486
7023974
7610851
8002000
8948565
9016381
9411291
9695406
30421755
1676056044
9075135300
101766230790
13784652882...

output:

1
(2,1) 
2
(3,1) (3,2) 
2
(4,1) (4,3) 
2
(5,1) (5,4) 
3
(4,2) (6,1) (6,5) 
2
(7,1) (7,6) 
2
(8,1) (8,7) 
2
(9,1) (9,8) 
4
(5,2) (5,3) (10,1) (10,9) 
4
(6,2) (6,4) (15,1) (15,14) 
6
(10,3) (10,7) (16,2) (16,14) (120,1) (120,119) 
8
(14,6) (14,8) (15,5) (15,10) (78,2) (78,76) (3003,1) (3003,3002) 
6
(...

result:

ok 200 lines