Jumlah Terbatas Edaran

10

Tantangan

Mari kita bayangkan sebuah N-tupel bilangan bulat antara 0 dan Minklusif, dan mari kita sebut saja F.

Ada (M + 1) ** Nkemungkinan Ftotal.

Berapa banyak yang Fmemenuhi semua ketidaksetaraan berikut (indeks berbasis satu)?

  • F[n] + F[n+1] <= M untuk 1 <= n < N
  • F[N] + F[1] <= M

Tulis sebuah program atau fungsi yang mengambil dua bilangan bulat positif N dan Mdan menghasilkan jawabannya dalam bentuk apa pun.

Uji Kasus

(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

Penjelasan

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)

Aturan

  • Ini adalah tantangan dengan . Kompleksitas waktu kode Anda harus polinomial dalam MdanN (mis. Anda tidak dapat menghasilkan semua (M + 1) ** Ntupel dan kemudian memeriksa kondisinya). Tolong jelaskan pendekatan Anda dalam pengiriman Anda.
  • Aturan standar berlaku. Jawaban terpendek dalam byte menang.
Bubbler
sumber

Jawaban:

7

Python dengan numpy , 59 byte

lambda M,N:trace(mat(tri(M+1)[::-1])**N)
from numpy import*

Cobalah online!

Menggunakan perkalian matriks untuk menghitung jalur. Jika presisi float adalah masalah, itu matbisa menentukan mat(...,int).

Tidak
sumber
Penggunaan mat(...,int)tampaknya tidak berfungsi untuk n=100kasus tersebut. Metode ini benar (menggunakan sympy untuk menjumlahkan kekuatan akar dari polinomial karakteristik tidak bekerja, misalnya), tetapi numpy salah di suatu tempat dengan meningkatnya angka (mungkin itu adalah **operator daya?)
Jonathan Allan
4

Pyth , 27 byte

.N?Ys:RTtYh-QNgQ+NTs:Rdtszh

Demonstrasi

Diharapkan input dalam format:

M
N

Ini adalah pemrograman dinamis klasik, di ujung kiri nilai yang ditetapkan sejauh ini, ujung kanan, dan ukuran kesenjangan saat ini.

Cara kerjanya, dalam pseudocode / 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))

Qdigunakan untuk M, zdigunakan untuk N, :adalah fill, Nadalah left, Tadalah right, Yadalah gap.

isaacg
sumber
4

MATL , 13 12 byte

Q:&>~PiY^Xds

Cobalah online! Ini adalah terjemahan langsung dari jawaban Python xnor dan jawaban MATL pertama saya, jadi kemungkinan besar tidak optimal. Misalnya ada kemungkinan cara yang lebih pendek untuk mendapatkan matriks segitiga kiri atas daripada t&lYRP. Sunting: Dan ternyata ada, yaitu :&>~P. Terima kasih kepada Luis Mendo untuk -1 byte!

               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
Laikoni
sumber
@LuisMendo Terima kasih! Meskipun hanya satu byte atau ada sesuatu yang bisa dijatuhkan?
Laikoni
1
Tidak, hanya itu, saya tidak bisa menghitung :-D
Luis Mendo
2

Stax , 17 byte

°(√&╒íƽ╨⌂'├╖▼1_Z

Jalankan dan debug itu

Dibongkar, tidak diserang, dan dikomentari, sepertinya ini.

^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

Jalankan yang ini

rekursif
sumber
2

R , 72 byte

function(M,N)sum(diag(Reduce(`%*%`,rep(list(outer(0:M,0:M,"+")<=M),N))))

Cobalah online!

Pendekatan port xnor.

Gagal untuk kasus uji yang lebih besar karena R hanya memiliki dukungan integer 32-bit (mereka dapat dilemparkan ke doublebegitu nilai maks tercapai), sehingga diperlukan gmpatau perpustakaan aritmatika presisi sewenang-wenang lainnya diperlukan.

Anehnya, R tidak memiliki operator daya matriks, seperti ^biasa berlaku elementwise.

Giuseppe
sumber
Sebenarnya, ada %^%operator yang diimplementasikan dengan benar dalam paket expmyang akan memungkinkan untuk -5 byte , tetapi sayangnya, itu tidak tersedia pada TIO (saya harus menguji secara lokal).
Kirill L.
@ KirillL. ya, saya sudah mempertimbangkan itu tapi saya pikir saya akan tetap dengan respons dasar R saya. Anda juga dapat melakukan golf hingga 60 byte dengan tidak memuat seluruh paket:function(M,N)sum(diag(expm::`%^%`(outer(0:M,0:M,"+")<=M,N)))
Giuseppe