하위 시퀀스는 임의의 양의 문자를 삭제하여 다른 시퀀스에서 얻을 수있는 시퀀스입니다. 의 별개의 비어 있지 않은 시퀀스 100이다 0, 1, 00, 10, 100. 의 별개의 비어 있지 않은 시퀀스가 1010있다 0, 1, 00, 01, 10, 11, 010, 100, 101, 110, 1010.
양의 정수를 제공하는 프로그램이나 기능을 쓰기 N 의 바이너리 확장 별개의 비어 있지 않은 서브 시퀀스의 수를 반환 N을 .
예 :부터 4이다 100진, 우리는 그렇게 다섯 별개의 비어 있지 않은 시퀀스 위에 있다고 보았다 f(4) = 5. 시작에서 N = 1 , 시퀀스가 시작된다 :
1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12
그러나 프로그램은 최신 머신에서 1 초 미만의 n <2 50 인치 동안 작동해야합니다 . 몇 가지 큰 예 :
f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
답변
파이썬 3 , 95 바이트 83 바이트
[Mr.XCoder 덕분에 -12 바이트 :)]
def f(x):
v=[2,1];c=1
for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
return c알고리즘에 대한 참고 사항. 알고리즘은 주어진 위치 (t)에서 비트에 의해 주어진 고유 한 서브 시퀀스의 증분을 계산한다. 첫 번째 비트의 증분은 항상 1입니다. 그런 다음 알고리즘은 비트 s (t)의 시퀀스를 실행하고 증분 v [s (t)]를 추가합니다. 각 단계에서 s (t), v [1-s (t)]의 보수에 대한 증분은 v [1] + v [0]으로 업데이트됩니다. 마지막 숫자는 모든 증분의 합입니다.
O (log2 (n))에서 실행해야합니다. 여기서 n은 입력 번호입니다.
답변
자바 스크립트 (ES6), 53 51 바이트
f=(n,r=~(a=[]))=>n<1?~r:f(n/2,r*2-~~a[n&=1],a[n]=r)테스트 사례
형식화 및 의견
f = ( // f is a recursive function taking:
n, // n = integer
r = ~( // r = last result, initially set to -1
a = [] // and using a[] = last results for 0 and 1,
) // implicitly initialized to [0, 0]
) => //
n < 1 ? // if n is less than 1:
~r // we're done: return -(r + 1)
: // else:
f( // do a recursive call with:
n / 2, // n / 2
r * 2 - ~~a[n &= 1], // updated result = r * 2 - last result for this binary digit
a[n] = r // update last result for this binary digit
) // end of recursive call비 재귀 버전, 63 바이트
@ThePirateBay 덕분에 3 바이트 절약
s=>[...s.toString(2)].map(l=c=>l[p=r,r=r*2-~~l[c],c]=p,r=1)|r-1테스트 사례
답변
파이썬 2 , 56 바이트
f=lambda x,a=1,b=1:x and f(x/2,a+~x%2*b,x%2*a+b)or a+b-2반복적으로 59 바이트 :
x=input()
v=[1,1]
while x:v[x%2]=sum(v);x/=2
print sum(v)-2답변
젤리 , 10 바이트
B3;BSṛ¦/’S
이것은 @NofP의 알고리즘 에서 @xnor의 개선 을 사용 합니다 .
배경
하자 (a는 1 , …하는 n은 ) 한정된 이진 시퀀스 일. 각각의 음이 아닌 정수를 들어 K ≤ N 정의 O K 고유 시퀀스의 수 (a 1 , …하는 K ) 중 하나를 비우거나 단부에 1 , Z의 K 이다 고유 시퀀스의 개수 비어 있거나 0으로 끝납니다 .
분명히, O 0 Z = 0 = 1 , 빈 시퀀스의 시퀀스 만이 빈 순서대로.
각 인덱스 k 에 대해 (a 1 , …, a k ) 의 총 서브 시퀀스 수 는 o k + z k -1입니다 ( 1을 빼면 o k 및 z k 가 빈 시퀀스를 계산 한다는 사실이 설명 됩니다). 비어 있지 않은 서브 시퀀스 의 총 수는 o k + z k -2 입니다. 이 과제는 o n + z n -2 를 계산하도록 요청합니다 .
마다는 K> 0 , 우리가 할 수있는 컴퓨팅 O K 및 Z의 K 재귀. 두 가지 경우가 있습니다.
-
a k = 1
z k = z k-1 이므로 (a 1 , …, k-1 ) 및 (a 1 , …, k-1 , 1) 은 0으로 끝나는 동일한 하위 시퀀스를 갖습니다 .
의 각각 O K – 1 의 비어 있지 않은 시퀀스 (a 1 , …하는 K ) 에 그 단부 1 우리 대열을 제거 할 수있는 한 것은 하나를 획득하기 위해 O K-1 + Z K-1 – 1 개의 서브 시퀀스 (a 1 , …, k-1 ) . 반대로, 첨부 1, 후자의 각각 O K-1 + Z K-1 – 1 개 중 하나의 서열 결과 O K – 1 개 전 서열. 따라서 o k -1 = oK-1 + Z K-1 – 1 과 O K = O K-1 + Z K-1 .
-
k는 0 =
이전의 경우와 마찬가지로 재귀 공식 o k = o k-1 및 z k = z k-1 + o k-1 을 얻습니다 .
작동 원리
B3;BSṛ¦/’S Main link. Argument: n (positive integer)
B Binary; convert n to base 2.
3; Prepend a 3.
B Binary; convert all integers in the resulting array to base 2, mapping
0 to [0], 1 to [1], and the prepended 3 to [1, 1].
/ Reduce the resulting array by the quicklink to the left, which will be
called with left argument [x, y] (integer pair) and right argument [j]
(either [0] or [1]).
¦ Sparse application.
S Compute the sum (x + y) and...
ṛ for each index in the right argument (i.e., for j)...
replace the element of [x, y] at that index with (x + y).
’ Decrement both integers in the resulting pair.
S Take the sum.
답변
05AB1E , 12 바이트
0¸sbvDO>yǝ}O
온라인으로 사용해보십시오! 설명 : AS는 다른 답변으로 지적 바이너리 문자열 시퀀스의 수를 a..y01에서 끝이 바이너리 문자열의 번호와 동일한 것으로 a..yA의 끝이 수하는 동안, 0진을위한 서브 시퀀스의 총 수는 문자열 a..y(각각 0접미사를 얻음 )에 1을 더한 문자열 0. 다른 답변과 달리 초기 상태를 구성하는 바이트를 저장하므로 빈 하위 시퀀스를 포함하지 않습니다.
0¸s Push [0] under the input
b Convert the input to binary
v } Loop over the digits
D Duplicate the array
O Take the sum
> Increment
yǝ Replace the index corresponding to the binary digit
O Take the sum of the final array
답변
자바 8, 97 바이트
n->f(n,1,1)long f(long n,long a,long b){return n>0?f(n/2,a+Math.floorMod(~n,2)*b,n%2*a+b):a+b-2;}포트 @xnor 의 파이썬 2 대답 차례의 개선, @NofP 의 파이썬 3 대답 ‘ .
어쩌면 제한된 시간 태그가 있는 것이 좋을 것입니다. 처음에 모든 하위 시퀀스를 무차별 처리하기 위해 다음을 수행했기 때문입니다.
import java.util.*;n->p(n.toString(n,2)).size()-1;Set p(String s){Set r=new HashSet();r.add("");if(s.isEmpty())return r;Set q=p(s.substring(1));r.addAll(q);for(Object o:q)r.add(""+s.charAt(0)+o);return r;}어느 것도 효과가 있었지만 마지막 세 가지 테스트 사례에는 너무 오래 걸렸습니다. 더 길다는 것은 말할 것도 없습니다 ( 208 204 바이트 ).
답변
6502 기계 코드 (C64), 321 바이트
00 C0 20 FD AE A2 00 9D 4F C1 E8 20 73 00 90 F7 9D 4F C1 A0 FF C8 B9 4F C1 D0
FA A2 15 CA 88 30 0A B9 4F C1 29 0F 9D 4F C1 10 F2 A9 00 9D 4F C1 CA 10 F8 A9
00 A0 07 99 64 C1 88 10 FA A0 40 A2 6C 18 BD E4 C0 90 02 09 10 4A 9D E4 C0 E8
10 F2 A2 07 7E 64 C1 CA 10 FA 88 F0 13 A2 13 BD 50 C1 C9 08 30 05 E9 03 9D 50
C1 CA 10 F1 30 D1 A2 0F A9 00 9D 3F C1 CA D0 FA A9 01 8D 3F C1 8D 47 C1 A2 08
CA BD 64 C1 F0 FA A0 09 1E 64 C1 88 90 FA B0 0A CA 30 28 A0 08 1E 64 C1 90 04
A9 47 B0 02 A9 4F 8D AF C0 86 FE A2 F8 18 BD 47 C0 7D 4F C0 9D 47 C0 E8 D0 F4
A6 FE 88 D0 DC F0 D5 A2 F8 BD 47 C0 7D 4F C0 9D 6C C0 E8 D0 F4 AD 64 C1 E9 01
8D 64 C1 A2 F9 BD 6C C0 E9 00 9D 6C C0 E8 D0 F5 A0 15 A9 00 99 4E C1 88 D0 FA
A0 40 A2 13 BD 50 C1 C9 05 30 05 69 02 9D 50 C1 CA 10 F1 0E 64 C1 A2 F9 3E 6C
C0 E8 D0 FA A2 13 BD 50 C1 2A C9 10 29 0F 9D 50 C1 CA 10 F2 88 D0 D1 E0 14 F0
06 E8 BD 4F C1 F0 F6 09 30 99 4F C1 C8 E8 E0 15 F0 05 BD 4F C1 90 F0 A9 00 99
4F C1 A9 4F A0 C1 4C 1E AB
오류 검사 기능이있는 온라인 데모 (346 바이트)
용법: sys49152,[n] 예 sys49152,911188917558917.
시간 제한 및 테스트 사례에는 64 비트 숫자로 계산하는 솔루션이 필요하므로 C64가 “ 현대 기계 “ 입니다 .
물론,이 코드의 꽤 필요 OS가 제공하지 않습니다 아무것도 16 비트보다 넓은 정수에 대해. 절름발이 부분 : 그것은 NofP 알고리즘 resp 의 또 다른 구현 (약간 수정)입니다 .xnor의 개선 된 변형 . 아이디어 주셔서 감사합니다;)
설명
다음은 알고리즘을 수행하는 관련 부품에 대한 주석 처리 된 분해 목록입니다.
.C:c06c A2 0F LDX #$0F ; 15 bytes to clear
.C:c06e A9 00 LDA #$00
.C:c070 .clearloop:
.C:c070 9D 3F C1 STA .num_a,X
.C:c073 CA DEX
.C:c074 D0 FA BNE .clearloop
.C:c076 A9 01 LDA #$01 ; initialize num_a and num_b
.C:c078 8D 3F C1 STA .num_a ; to 1
.C:c07b 8D 47 C1 STA .num_b
.C:c07e A2 08 LDX #$08 ; 8 bytes of input to check,
.C:c080 .findmsb: ; start at most significant
.C:c080 CA DEX
.C:c081 BD 64 C1 LDA .nc_num,X
.C:c084 F0 FA BEQ .findmsb ; repeat until non-0 byte found
.C:c086 A0 09 LDY #$09 ; 8 bits to check (+1 for pre dec)
.C:c088 .findbit:
.C:c088 1E 64 C1 ASL .nc_num,X ; shift left, highest bit to carry
.C:c08b 88 DEY
.C:c08c 90 FA BCC .findbit ; bit was zero -> repeat
.C:c08e B0 0A BCS .loopentry ; jump into calculation loop
.C:c090 .mainloop:
.C:c090 CA DEX ; next byte
.C:c091 30 28 BMI .done ; index -1? -> done calculating
.C:c093 A0 08 LDY #$08 ; 8 bits to check
.C:c095 .bitloop:
.C:c095 1E 64 C1 ASL .nc_num,X ; shift left, highest bit to carry
.C:c098 90 04 BCC .tgt_b ; if 0, store addition result in num_b
.C:c09a .loopentry:
.C:c09a A9 47 LDA #$47
.C:c09c B0 02 BCS .tgt_a ; ... else store in num_a ...
.C:c09e .tgt_b:
.C:c09e A9 4F LDA #$4F
.C:c0a0 .tgt_a:
.C:c0a0 8D AF C0 STA $C0AF ; ... using self-modification.
.C:c0a3 86 FE STX $FE ; save byte index
.C:c0a5 A2 F8 LDX #$F8 ; index for adding
.C:c0a7 18 CLC
.C:c0a8 .addloop:
.C:c0a8 BD 47 C0 LDA $C047,X ; load byte from num_a
.C:c0ab 7D 4F C0 ADC $C04F,X ; add byte from num_b
.C:c0ae 9D 47 C0 STA $C047,X ; store to num_a or num_b
.C:c0b1 E8 INX ; next index
.C:c0b2 D0 F4 BNE .addloop ; done if index overflown
.C:c0b4 A6 FE LDX $FE ; restore byte index
.C:c0b6 88 DEY ; decrement bit index
.C:c0b7 D0 DC BNE .bitloop ; bits left in current byte -> repeat
.C:c0b9 F0 D5 BEQ .mainloop ; else repeat main loop
.C:c0bb .done:
.C:c0bb A2 F8 LDX #$F8 ; index for adding
.C:c0bd .addloop2:
.C:c0bd BD 47 C0 LDA $C047,X ; load byte from num_a
.C:c0c0 7D 4F C0 ADC $C04F,X ; add byte from num_b
.C:c0c3 9D 6C C0 STA $C06C,X ; store to nc_num (result)
.C:c0c6 E8 INX ; next index
.C:c0c7 D0 F4 BNE .addloop2 ; done if index overflown
.C:c0c9 AD 64 C1 LDA .nc_num ; load least significant result byte
.C:c0cc E9 01 SBC #$01 ; subtract 2 (1 + negated carry)
.C:c0ce 8D 64 C1 STA .nc_num ; store least significant result byte
.C:c0d1 A2 F9 LDX #$F9 ; index for subtract
.C:c0d3 .subloop:
.C:c0d3 BD 6C C0 LDA $C06C,X ; subtract 0 from all other bytes
.C:c0d6 E9 00 SBC #$00 ; for handling carry if necessary
.C:c0d8 9D 6C C0 STA $C06C,X
.C:c0db E8 INX
.C:c0dc D0 F5 BNE .subloop
나머지는 입 / 출력이며 더블 더블 알고리즘을 사용하여 문자열과 64 비트 부호없는 정수 (little-endian) 사이에서 변환됩니다. 관심이 있으시다면, 여기에 오류 검사 기능이있는 버전의 전체 어셈블리 소스가 있습니다. . “golfed”버전은 “golf”브랜치에 있습니다.