Somas limitadas circulares

10

Desafio

Vamos imaginar um número Nmúltiplo de números inteiros entre 0 e Minclusivo, e vamos chamá-lo F.

Existem s (M + 1) ** Npossíveis Fno total.

Quantos desses Fs satisfazem todas as seguintes desigualdades (o índice é baseado em um)?

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

Escreva um programa ou função que leva dois inteiros positivos N e Me envia a resposta de qualquer forma conveniente.

Casos de teste

(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

Explicação

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)

Regras

  • Este é um desafio de . A complexidade do tempo do seu código deve ser polinomial MeN (por exemplo, você não pode gerar todas as (M + 1) ** Ntuplas e verificar a condição). Por favor, explique sua abordagem ao enviar.
  • Aplicam-se as regras de padrão . A resposta mais curta em bytes vence.
Bubbler
fonte

Respostas:

7

Python com numpy , 59 bytes

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

Experimente online!

Usa multiplicação de matrizes para contar caminhos. Se a precisão da flutuação for um problema, o matpoderia especificar mat(...,int).

xnor
fonte
O uso mat(...,int)não parece funcionar para os n=100casos. O método é correta (usando SymPy para somar as potências das raízes do polinômio característico funciona, por exemplo), mas numpy vai em algum lugar errado, como os números aumentam (talvez seja o **operador de potência?)
Jonathan Allan
4

Pitão , 27 bytes

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

Demonstração

Espera entrada no formato:

M
N

Essa é uma programação dinâmica clássica, na extremidade esquerda dos valores definidos até agora, na extremidade direita e no tamanho atual da lacuna.

Como funciona, no pseudocódigo / 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é usado para M, zé usado para N, :é fill, Né left, Té right, Yé gap.

isaacg
fonte
4

MATL , 13 12 bytes

Q:&>~PiY^Xds

Experimente online! Esta é uma tradução direta da resposta Python do xnor e da minha primeira resposta MATL, portanto, provavelmente não é o ideal. Por exemplo, é provável que haja uma maneira mais curta de obter uma matriz triangular superior esquerda do que t&lYRP. Edit: E acontece que existe, a saber :&>~P. Obrigado a Luis Mendo por -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
fonte
@LuisMendo Thanks! Embora seja apenas um byte ou há outra coisa que pode ser descartada?
Laikoni
11
Não, é isso, eu não posso contar :-D
Luis Mendo
2

Stax , 17 bytes

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

Execute e depure

Descompactado, não jogado e comentado, parece com isso.

^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

Execute este

recursivo
fonte
2

R , 72 bytes

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

Experimente online!

Portos abordagem xnor.

Falha em casos de teste maiores, já que o R tem apenas suporte inteiro de 32 bits (eles são convertidos para doublequando o valor máximo de int for atingido), portanto, gmpseria necessário o uso de outra biblioteca aritmética de precisão arbitrária.

Estranhamente, R não possui um operador de matriz, como ^sempre se aplica aos elementos.

Giuseppe
fonte
Na verdade, há um %^%operador corretamente implementado no pacote expmque permitiria -5 bytes , mas, infelizmente, ele não está disponível no TIO (eu tive que testar localmente).
Kirill L.
@KirillL. Sim, eu tinha considerado isso, mas acho que vou ficar com a minha resposta R. de base. Além disso, você pode jogar até 60 bytes por não carregar no pacote inteiro:function(M,N)sum(diag(expm::`%^%`(outer(0:M,0:M,"+")<=M,N)))
Giuseppe