도전
N
0과 M
포괄적 인 정수 의 튜플을 상상해 봅시다 F
.
있습니다 (M + 1) ** N
가능한 F
총들.
F
다음의 모든 부등식을 모두 충족 하는 그러한 요소는 몇 개입니까 (인덱스는 1 기준)?
F[n] + F[n+1] <= M
…에 대한1 <= n < N
F[N] + F[1] <= M
두 취하는 함수 작성 프로그램 또는 양의 정수를 N
그리고 M
어떤 편리한 형태로 응답을 출력한다.
테스트 사례
(N,M) => Answer
(1,1) => 1
(2,1) => 3
(3,1) => 4
(4,1) => 7
(1,2) => 2
(2,2) => 6
(3,2) => 11
(4,2) => 26
(10,3) => 39175
(10,4) => 286555
(10,5) => 1508401
(25,3) => 303734663372
(25,4) => 43953707972058
(25,5) => 2794276977562073
(100,3) => 8510938110502117856062697655362747468175263710
(100,4) => 3732347514675901732382391725971022481763004479674972370
(100,5) => 60964611448369808046336702581873778457326750953325742021695001
설명
M (max value of element) = 1
F[1] + F[1] <= 1; F = [0]
(1,1) => 1
F[1] + F[2] <= 1; F = [0,0], [0,1], [1,0]
(2,1) => 3
F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) => 4
F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) => 7
---
M = 2
F[1] + F[1] <= 2; F = [0], [1]
(1,2) => 2
F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) => 6
F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) => 11
(4,2) => 26 (left as exercise for you)
규칙
답변
파이썬 과 NumPy와 59 바이트
lambda M,N:trace(mat(tri(M+1)[::-1])**N)
from numpy import*
행렬 곱셈을 사용하여 경로를 계산합니다. float 정밀도가 문제인 mat
경우을 지정할 수 mat(...,int)
있습니다.
답변
Pyth , 27 바이트
.N?Ys:RTtYh-QNgQ+NTs:Rdtszh
다음 형식으로 입력을 예상합니다.
M
N
이것은 지금까지 설정된 값의 왼쪽 끝, 오른쪽 끝 및 현재 간격의 크기에 대한 고전적인 동적 프로그래밍입니다.
의사 코드 / Python에서 작동 방식 :
.N | define memoized fill(left, right, gap):
? | if cap > 0 then
s:RTtY | sum(fill(i, right, gap - 1)
h-QN | for i in range(M - left + 1))
gQ+NT | else M >= left + right
| output:
s:Rdtsz | sum(fill(i, i, N - 1)
h | for i in range(M + 1))
Q
에 사용되는 M
, z
사용되는 N
, :
있다 fill
, N
있다 left
, T
있다 right
, Y
있다 gap
.
답변
MATL , 13 12 바이트
Q:&>~PiY^Xds
온라인으로 사용해보십시오! 이것은 xnor의 Python 답변 과 첫 번째 MATL 답변을 직접 번역 한 것이므로 최적이 아닙니다. 예를 들어보다 왼쪽 위의 삼각 행렬을 얻는 더 짧은 방법이있을 수 있습니다 t&lYRP
. 편집 : 그리고 거기에 :&>~P
있습니다. -1 바이트의 Luis Mendo에게 감사합니다!
M is the first input and N the second
Q: increment M and generate range from 1 to M+1
&> compare vector element wise with itself with greater-than function
results in a upper-right triangular matrix
~ inverse to get lower-left triangular matrix
P flip rows to get upper-left triangular matrix
i input N
Y^ take the matrix to the power of N
Xds compute the sum of the main diagonal
답변
Stax , 17 바이트
°(√&╒íƽ╨⌂'├╖▼1_Z
포장을 풀고 포장을 풀고 주석을 달았습니다.
^1]( [1, 0, ... 0] with M zeroes
:) get all rotations of the array
{ begin block
{:+rm map each array to reverse(prefixSums(arr))
},v* execute preceding block N-1 times
F for each array, execute the rest of the program
iT remove the last i elements from the array, where i is the iteration index
F+ add the remaining elements to the running total
implicitly print output
답변
R , 72 바이트
function(M,N)sum(diag(Reduce(`%*%`,rep(list(outer(0:M,0:M,"+")<=M),N))))
포트 xnor의 접근 방식.
R은 32 비트 정수만 지원 double
하므로 (최대 int 값에 도달 하면 캐스트 됨) 더 큰 테스트 사례에서는 실패 하므로 gmp
다른 임의의 정밀 산술 라이브러리를 사용해야합니다.
이상하게도 R은 ^
항상 요소 단위 로 적용되는 행렬 전력 연산자가 없습니다 .