Pelat Lisensi Sempurna

33

Pelat Lisensi Sempurna

Mulai beberapa tahun yang lalu, saya membuat permainan kecil saat mengemudi: memeriksa apakah plat nomor terdekat "sempurna". Ini relatif jarang, tetapi menyenangkan ketika Anda menemukannya.

Untuk memeriksa apakah plat nomornya sempurna:

  1. Ringkas karakter, dengan A = 1, B = 2, ... Z = 26.
  2. Ambil setiap potongan angka berturut-turut, dan jumlahkan; kalikan masing-masing jumlah ini bersama-sama.

Jika nilai di bagian 1 dan bagian 2 sama, selamat! Anda telah menemukan plat nomor sempurna!

Contohnya

License plate: AB3C4F

Digits -> 3 * 4 
        = 12
Chars  -> A + B + C + F 
        = 1 + 2 + 3 + 6 
        = 12
12 == 12 -> perfect!


License plate: G34Z7T

Digits -> (3 + 4) * 7 
        = 49
Chars  -> G + Z + T 
        = 7 + 26 + 20 
        = 53
49 != 53 -> not perfect!


License plate: 10G61

Digits -> (1 + 0) * (6 + 1)
        = 7
Chars  -> G
        = 7
7 == 7 -> perfect!

Tantangan

Saya menggunakan plat nomor dengan panjang 5 dan 6 sebagai contoh, tetapi prosedur ini berlaku untuk semua panjang plat. Tantangan Anda adalah, untuk panjang tertentu N, kembalikan jumlah plat nomor yang sempurna dengan panjang itu. Untuk tujuan tantangan, plat nomor yang valid adalah kombinasi angka 0-9 dan karakter AZ. Piring harus berisi karakter dan angka agar dianggap berpotensi sempurna. Untuk tujuan pengecekan, berikut adalah nilai yang saya dapatkan (meskipun saya tidak bisa 100% tentang kebenarannya, hahaha)

N < 2: 0
N = 2: 18
N = 3: 355
N = 4: 8012 

Catatan

Jika entah bagaimana itu membuat masalah lebih sederhana dalam bahasa Anda, Anda dapat menampilkan proporsi plat nomor sempurna untuk N yang diberikan, setidaknya 2 digit signifikan.

N < 2: 0
N = 2: 0.0138888...
N = 3: 0.0076088...
N = 4: 0.0047701...

ATAU, Anda dapat menampilkan nilai setara mod 256

N < 2: 0
N = 2: 18
N = 3: 99
N = 4: 76

Kemenangan terpendek!

Akan menjadi
sumber
2
Selamat datang di situs ini! Saya pikir ini adalah tantangan yang baik, tetapi output tambahan yang diizinkan membuatnya sulit untuk benar-benar mencetak jawaban. PPCG mencari kriteria kemenangan yang objektif, dan sulit untuk melakukannya ketika ada begitu banyak kebebasan; ini tidak hanya mengubah format output, ini sebenarnya mengubah apa yang Anda boleh output. Saya akan merekomendasikan untuk mengedit opsi lain dan hanya membuatnya diperlukan untuk menampilkan jumlah plat yang sempurna N.
HyperNeutrino
11
Saya pribadi akan lebih menikmati tantangan ini jika itu hanya memvalidasi apakah plat nomor yang diberikan adalah sempurna atau tidak (terutama karena Anda tidak memiliki angka pasti untuk kasus uji. Mungkin tidak masalah, selama potensi hasil yang dihitung berkurang. Tidak yakin tentang bagaimana perasaan orang lain. Ide bagus sekalipun!
MildlyMilquetoast
4
Saya setuju dengan Mistah Figgins; Saya merasa seperti ini lebih tentang menemukan pola, yang masih merupakan tantangan yang menarik, tetapi saya pikir itu mungkin menarik lebih banyak jawaban jika itu hanya pemeriksaan validasi. Tantangan yang bagus!
HyperNeutrino
1
Saya telah memposting tantangan yang berkaitan erat , berharap itu akan menarik perhatian pada pertanyaan indah ini, serta menyederhanakan ini sedikit, hanya memeriksa (hampir) plat nomor yang sempurna.
Tn. Xcoder
1
@cococuting Saya mencoba yang terbaik tetapi ternyata kosong. Saya mengirimkannya ke guru matematika saya dan sejauh ini dia masih kosong
Christopher

Jawaban:

9

Python 3.6, 150 byte

f=lambda n,t=-1,p=-1,a=0:sum(f(n-1,*((t,c+p*(p>=0),a),((t<0 or t)*(p<0 or p),-1,a-c))[c<0])for c in range(-26,10))if n else 0<(t<0 or t)*(p<0 or p)==a

hasil:

f(2) = 18
f(3) = 355
f(4) = 8012
f(5) = 218153

Versi tidak dikoleksi dengan penjelasan:

digits=[*range(10)]
letters=[*range(1,27)]

def f(n, dt=-1, dp=-1, lt=0):
    if n:
        for d in digits:
            yield from f(n - 1,
                         dt,
                         d if dp < 0 else dp + d,
                         lt
                         )

        for l in letters:
            yield from f(n - 1,
                         dp if dt < 0 else dt if dp < 0 else dt*dp,
                         -1,
                         lt + l
                         )
    else:
        yield 0 < lt == (dt<0 or dt)*(dp<0 or dp)

Masalahnya bermuara pada pencarian pohon di mana setiap tingkat pohon sesuai dengan posisi dalam nomor plat dan setiap node memiliki 36 anak (10 digit dan 26 huruf). Fungsi melakukan pencarian pohon secara rekursif, mengumpulkan nilai untuk digit dan huruf saat berjalan.

n is the number of levels to search. 
dp accumulates the sum of a group of digits.
dt accumulates the product of the digit sums.
lt accumulates the sum of the letter values.

For dp and dt, a value < 0 indicates it is not initialized.

Termasuk Golf, mengonversi loop for menjadi jumlah generator:

sum(f(n-1, 
      dt,
      d if dp < 0 else dp + d,
      lt) for d in digits)
+
sum(f(n-1,
      dp if dt<0 else dt if dp<0 else dt*dp,
      -1,
      lt+l) for l in letters)

Kemudian menggabungkan generator. Encode huruf, A ke Z, sebagai -1 hingga -26 dan digit sebagai 0 hingga 9. Jadi jumlahnya menjadi:

sum(f(n-1, *args) for c in range(-26, 10)),

dimana args adalah:

((dp if dt<0 else dt if dp<0 else dt*dp, -1, lt-l) if c <0 else
 (dt, d if dp<0 else dp+d, lt))

Sisa golf adalah mengubah fungsi menjadi lambda, memperpendek nama variabel, dan menyederhanakan ekspresi.

RootTwo
sumber
Ini adalah solusi yang fasih, apa jadinya runtime? n*n*log(n)atau yang serupa?
Magic Gurita Guci
@cococuting Terima kasih. Solusi masih menghasilkan semua kemungkinan permutasi dari panjang yang diberikan, sehingga memiliki kompleksitas yang sama dengan solusi lainnya. Sesuatu seperti k ** n, di mana k adalah jumlah simbol dalam alfabet (misalnya, 10 digit + 26 huruf = 36) dan n adalah jumlah simbol pada plat nomor. Menjalankannya untuk n = 5 membutuhkan pemeriksaan 36 ^ 5 = 60.466.176 permutasi dan membutuhkan satu atau dua menit (memoisasi mungkin mempercepatnya, tetapi akan membutuhkan banyak byte ;-)).
RootTwo
6

Dyalog APL, 57 56 byte

+/(+/0⌈a-9)=×/c*⍨-2-/0,⌈\(+\a×b)×c←2>/0,⍨b←9≥a←↑1↓,⍳⎕⍴36

(mengasumsikan ⎕io←0)

amatriks semua plat nomor yang valid (kecuali 00...0) dikodekan dengan: 0-9 untuk digit, 10-35 untuk huruf

b bitmask untuk tempat digit terjadi

c bitmask untuk digit terakhir di setiap grup digit berurutan

ngn
sumber
Cobalah online untuk 1-4 membutuhkan lebih banyak memori untuk 4, tetapi ada juga cara lain!
Adám
4

Python 2, 359 295 byte

Agak panjang; ini adalah solusi sepele. Saya yakin ini benar, meskipun tidak cocok dengan kasus uji dalam tantangan. Solusi yang saya dapatkan cocok dengan jawaban Dada.

import itertools as i,re as r,string as s
print len([''.join(x)for x in i.product(s.lowercase+s.digits,repeat=input())if(lambda t:r.search('\\D',t)and r.search('\\d',t)and reduce(int.__mul__,[sum(map(int,k))for k in r.split('\\D+',t)if k])==sum([k-96 for k in map(ord,t) if k>96]))(''.join(x))])

-64 byte berkat saran dari @numbermaniac

HyperNeutrino
sumber
1
Anda dapat menyimpan sekitar tiga byte dalam c (x) dan baris terakhir; menghapus ruang antara 96 ​​dan for; antara map(ord,x)dan if; dan di baris terakhir, antara .join(x)dan for. Saya pikir Anda juga dapat menyimpan lebih banyak jika Anda mendefinisikan kembali fungsi ke lambdas.
numbermaniac
@numbermaniac Terima kasih! (Total 64 byte)
HyperNeutrino
4

Python 2 , 291 287 276 273 byte

lambda n:sum(1for x in s.product(y+z,repeat=n)if(lambda p,s=set:reduce(int.__mul__,[sum(map(int,i))for i in re.findall(r"\d+",p)],1)==sum(ord(i)-64for i in p if ord(i)>64)and s(p)&s(y)and s(p)&s(z))(''.join(x)))
import re,itertools as s,string as t
y=t.uppercase
z=t.digits

Cobalah online!


Hasil:

0 0
1 0
2 18
3 355
4 8012
ovs
sumber
3

Perl 5 , 117 byte

116 byte kode + -pbendera.

$"=",";@F=(A..Z,0..9);map{$r=1;$r*=eval s/./+$&/gr for/\d+/g;$r+=64-ord for/\pl/g;$\+=!$r*/\pl/*/\d/}glob"{@F}"x$_}{

Cobalah online!

Rasanya cukup optimal, tapi saya kehabisan ide sekarang.
Kode itu sendiri sangat tidak efisien karena menghitung setiap permutasi a..z,0..9panjang n(dibutuhkan sekitar 1 detik untuk n=3, ~ 15 detik untuk n=4dan ~ 7 menit untuk n=5).
Algoritma ini cukup lurus ke depan: untuk setiap kemungkinan ukuran pelat n(dihasilkan dengan glob"{@F}"x$_- globoperatornya cukup ajaib), $r*=eval s/./+$&/gr for/\d+/g;menghitung produk dari setiap bilangan digit, dan $r+=64-ord for/\pl/gmengurangi bobot huruf-hurufnya. Kemudian, kami menambah penghitung $\jika $ris 0( !$r) dan jika pelat berisi angka dan huruf ( /\pl/*/\d/). $\dicetak secara implisit di akhir berkat -pbendera.

Perhatikan bahwa nomor saya mendapatkan yang n=2 -> 18, n=3 -> 355, n=4 -> 8012, n=5 -> 218153. Saya cukup yakin ini adalah yang benar, tetapi saya mungkin salah, dalam hal ini beri tahu saya dan saya akan menghapus jawaban ini.

Dada
sumber
3

APL (Dyalog) , 71 byte

Tubuh program penuh. Prompt untuk N. N≥4 membutuhkan banyak memori dan perhitungan.

+/((+/⊢⍳∩)∘⎕A=(×/'\d+'S{+/⍎¨⍵.Match}))¨l/⍨∧⌿∨/¨c∘.∊l←,(∊c←⎕DA)∘.,⍣⎕⊂⍬

Cobalah online!

Adm
sumber
2

Scala, 265 byte

(n:Int)=>{val i=('A'to'Z')++('0'to'9');Seq.fill(n)(i).flatten.combinations(n).flatMap(_.permutations).map(_.mkString).count(l=>"(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size>0&&l.map(_-64).filter(_>0).sum==l.split("[A-Z]").filter(""<).map(_.map(_-48).sum).reduce(_*_))}

Penjelasan:

(n:Int) => {
    val i = ('A' to 'Z') ++ ('0' to '9');                       // All license plates available characters.
    Seq.fill(n)(i).flatten                                      // Simulate combination with repetition (each character is present n times)
        .combinations(n)                                        // and generate all combinations of size n (all license plates).
        .flatMap(_.permutations)                                // For each combination, generate all permutations (ex. : Seq('A', '1') => Seq('A', '1') and Seq('1', 'A')), and
        .map(_.mkString)                                        // convert each permutation to String (Seq('A', '1') => "A1").
        .count ( l =>                                           // Then count all strings having :
            "(?=.*[A-Z])(?=.*\\d)".r.findAllIn(l).size > 0 &&   // at least 1 character and 1 digit and
            l.map(_ - 64).filter(_ > 0).sum ==                  // a sum of characters (> 'A' or > 64) equals to
            l.split("[A-Z]").filter(""<)
                .map(_.map(_ - 48).sum)
                .reduce(_*_)                                    // the product of sum of digits groups (split String by letters to get digits groups)
        )
}

Catatan:

  • -64dan -48digunakan untuk mengubah Char(masing-masing surat dan digit) ke nya Intnilai ( 'A' - 64 = 1, 'B' - 64 = 2, ..., '9' - 48 = 9)
  • Filter dalam l.split("[A-Z]").filter(""<)digunakan untuk menghilangkan ""nilai jika ldimulai dengan huruf (contoh "A1".split("[A-Z]") => Array("", 1):). Mungkin ada solusi yang lebih baik dan lebih pendek

Kasus uji:

val f = (n:Int) => ...  // assign function
(1 to 5).foreach ( i =>
    println(s"N = $i: ${f(i)}")
)

Hasil:

N = 1: 0
N = 2: 18
N = 3: 355
N = 4: 8012
N = 5: 218153

Fungsi ini cukup lambat n > 4karena semua kombinasi harus dibuat.

norbjd
sumber
2

Java, 382 365 byte

  • Disimpan 17 byte, terima kasih kepada Kevin Cruijssen

Golf

int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}
int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}
int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}
int s(int n){return f("",n);}

Terperinci

// return sum of adjecent digits
int h(String s)
{
    int sum = 0;
    for(char c : s.toCharArray()) sum += c-'0';
    return sum;
}

// check if perfect
int g(String t)
{
    int d = 1;
    int c = 0;

    for(String s : t.split("[^0-9]")) d *= h(s);
    for(String s : t.split("[^A-Z]")) c += s.charAt(0)-'A';

    return d == c ? 1 : 0;
}

// tree of enumerations
int f(String t, int n)
{
    // base case
    if(t.length() == n)
    {
        return g(t);
    }

    // enumeration
    int sum = 0;
    for(char d='0'; d<='9'; d++) sum += f(t+d, n);
    for(char c='A'; c<='Z'; c++) sum += f(t+c, n);

    return sum;
}

int s(int n){ return f("",n); }
Khaled.K
sumber
Saya pikir Anda memerlukan fungsi yang hanya membutuhkan ninput.
Christian Sievers
@ChristianSievers
1
Beberapa hal untuk golf untuk kode Anda saat ini: int h(String s){int m=0;for(int c:s.toCharArray())m+=c-48;return m;}int g(String t){int d=1,c=0;for(String s:t.split("[^0-9]"))d*=h(s);for(String s:t.split("[^A-Z]"))c+=s.charAt(0)-65;return d==c?1:0;}int f(String t,int n){int m=0;if(t.length()==n)return g(t);for(int d=48;d<58;)m+=f(t+d++,n);for(int c=65;c<91;)m+=f(t+c++,n);return m;}int s(int n){return f("",n);}( 365 bytes ) Anda dapat membandingkan versi Anda saat ini dengan yang ini untuk melihat perubahan yang saya lakukan (terlalu banyak untuk dicocokkan dengan sisa komentar ini). :)
Kevin Cruijssen
@KevinCruijssen thx, 17 byte sekarang
Khaled.K
2

GAP , 416 byte

Tidak akan menang pada ukuran kode, dan jauh dari waktu yang konstan, tetapi menggunakan matematika untuk mempercepat banyak!

x:=X(Integers);
z:=CoefficientsOfUnivariatePolynomial;
s:=Size;

f:=function(n)
 local r,c,p,d,l,u,t;
 t:=0;
 for r in [1..Int((n+1)/2)] do
  for c in [r..n-r+1] do
   l:=z(Sum([1..26],i->x^i)^(n-c));
   for p in Partitions(c,r) do
    d:=x;
    for u in List(p,k->z(Sum([0..9],i->x^i)^k)) do
     d:=Sum([2..s(u)],i->u[i]*Value(d,x^(i-1))mod x^s(l));
    od;
    d:=z(d);
    t:=t+Binomial(n-c+1,r)*NrArrangements(p,r)*
         Sum([2..s(d)],i->d[i]*l[i]);
   od;
  od;
 od;
 return t;
end;

Untuk memeras ruang kosong yang tidak perlu dan mendapatkan satu baris dengan 416 byte, pipa melalui ini:

sed -e 's/^ *//' -e 's/in \[/in[/' -e 's/ do/do /' | tr -d \\n

Laptop lama "dirancang untuk Windows XP" saya dapat menghitung f(10)dalam waktu kurang dari satu menit dan melangkah lebih jauh dalam waktu kurang dari satu jam:

gap> for i in [2..15] do Print(i,": ",f(i),"\n");od;
2: 18
3: 355
4: 8012
5: 218153
6: 6580075
7: 203255386
8: 6264526999
9: 194290723825
10: 6116413503390
11: 194934846864269
12: 6243848646446924
13: 199935073535438637
14: 6388304296115023687
15: 203727592114009839797

Bagaimana itu bekerja

Misalkan kita pertama-tama hanya ingin mengetahui jumlah plat nomor yang cocok dengan pola LDDLLDL, di mana Lmenunjukkan suatu huruf dan Dmenunjukkan suatu angka. Asumsikan kita memiliki daftar langka sehingga l[i]memberikan jumlah cara huruf dapat memberikan nilai i, dan daftar serupa duntuk nilai yang kita dapatkan dari angka. Maka jumlah plat nomor sempurna dengan nilai umum iadalah adil l[i]*d[i], dan kami mendapatkan nomor plat nomor sempurna dengan pola kami dengan menjumlahkan ini semua i. Mari kita tunjukkan operasi mendapatkan jumlah ini pada l@d.

Sekarang bahkan jika cara terbaik untuk mendapatkan daftar ini adalah dengan mencoba semua kombinasi dan menghitung, kita dapat melakukan ini secara independen untuk huruf dan digit, melihat 26^4+10^3case daripada 26^4*10^3 case ketika kita menjalankan semua pelat yang sesuai dengan pola. Tetapi kita dapat melakukan jauh lebih baik: lhanya daftar koefisien di (x+x^2+...+x^26)^kmana kjumlah huruf, di sini 4.

Demikian pula, kita mendapatkan jumlah cara untuk mendapatkan jumlah digit dalam rangkaian kdigit sebagai koefisien (1+x+...+x^9)^k. Jika ada lebih dari satu putaran digit, kita perlu menggabungkan daftar terkait dengan operasi d1#d2yang pada posisi imemiliki nilai jumlah dari semua d1[i1]*d2[i2]tempat i1*i2=i. Ini adalah konvolusi Dirichlet, yang hanya merupakan produk jika kita menafsirkan daftar sebagai koefisien dari seri Dirchlet. Tapi kami sudah menggunakannya sebagai polinomial (seri daya terbatas), dan tidak ada cara yang baik untuk menafsirkan operasi untuk mereka. Saya pikir ketidakcocokan ini adalah bagian dari apa yang membuatnya sulit untuk menemukan formula sederhana. Mari kita gunakan pada polinomial dan gunakan notasi yang sama #. Sangat mudah untuk menghitung ketika satu operan adalah monomial: yang kita milikip(x) # x^k = p(x^k). Bersamaan dengan fakta bahwa itu bilinear, ini memberikan cara yang bagus (tapi tidak sangat efisien) untuk menghitungnya.

Perhatikan bahwa khuruf memberikan nilai paling banyak 26k, sedangkan k angka tunggal dapat memberikan nilai 9^k. Jadi kita akan sering mendapatkan kekuatan tinggi yang tidak dibutuhkan dalam dpolinomial. Untuk menghilangkannya, kita dapat menghitung modulo x^(maxlettervalue+1). Ini memberi kecepatan besar dan, meskipun saya tidak segera menyadarinya, bahkan membantu bermain golf, karena kita sekarang tahu bahwa derajatnya dtidak lebih besar daripada tingkat l, yang menyederhanakan batas atas di final Sum. Kami mendapatkan kecepatan yang lebih baik dengan melakukan modperhitungan pada argumen pertama Value (lihat komentar), dan melakukan keseluruhan #perhitungan pada level yang lebih rendah memberikan kecepatan yang luar biasa. Tapi kami masih berusaha menjadi jawaban yang sah untuk masalah golf.

Jadi kita sudah mendapat kami ldan ddan dapat menggunakannya untuk menghitung jumlah plat sempurna dengan pola LDDLLDL. Itu adalah angka yang sama dengan polanya LDLLDDL. Secara umum, kita dapat mengubah urutan deretan digit dengan panjang berbeda sesuai keinginan, NrArrangementsmemberikan jumlah kemungkinan. Dan sementara harus ada satu huruf di antara deretan angka, surat-surat lainnya tidak tetap. The Binomialmenghitung kemungkinan ini.

Sekarang tinggal menjalankan semua cara yang mungkin untuk memiliki panjang digit angka. rdijalankan melalui semua jumlah run, cmelalui semua jumlah total digit, dan pmelalui semua partisi cdengan rpuncak.

Jumlah total partisi yang kita lihat adalah dua kurang dari jumlah partisi n+1, dan fungsi partisi bertambah exp(sqrt(n)). Jadi sementara masih ada cara mudah untuk meningkatkan waktu berjalan dengan menggunakan kembali hasil (menjalankan melalui partisi dalam urutan yang berbeda), untuk peningkatan mendasar kita perlu menghindari melihat setiap partisi secara terpisah.

Menghitungnya dengan cepat

Catat itu (p+q)@r = p@r + q@r. Dengan sendirinya, ini hanya membantu menghindari beberapa perkalian. Tetapi bersamaan dengan (p+q)#r = p#r + q#ritu berarti bahwa kita dapat menggabungkan dengan polinomial penambahan sederhana yang sesuai dengan partisi yang berbeda. Kita tidak bisa menambahkan semuanya, karena kita masih perlu tahu dengan mana lkita harus @-kombinasi, faktor mana yang harus kita gunakan, dan #ekstensi- mana yang masih mungkin.

Mari kita gabungkan semua polinomial yang sesuai dengan partisi dengan jumlah dan panjang yang sama, dan sudah memperhitungkan berbagai cara untuk mendistribusikan panjang lintasan digit. Berbeda dari yang saya berspekulasi dalam komentar, saya tidak perlu peduli dengan nilai yang digunakan terkecil atau seberapa sering digunakan, jika saya memastikan bahwa saya tidak akan memperpanjang dengan nilai itu.

Ini kode C ++ saya:

#include<vector>
#include<algorithm>
#include<iostream>
#include<gmpxx.h>

using bignum = mpz_class;
using poly = std::vector<bignum>;

poly mult(const poly &a, const poly &b){
  poly res ( a.size()+b.size()-1 );
  for(int i=0; i<a.size(); ++i)
    for(int j=0; j<b.size(); ++j)
      res[i+j]+=a[i]*b[j];
  return res;
}

poly extend(const poly &d, const poly &e, int ml, poly &a, int l, int m){
  poly res ( 26*ml+1 );
  for(int i=1; i<std::min<int>(1+26*ml,e.size()); ++i)
    for(int j=1; j<std::min<int>(1+26*ml/i,d.size()); ++j)
      res[i*j] += e[i]*d[j];
  for(int i=1; i<res.size(); ++i)
    res[i]=res[i]*l/m;
  if(a.empty())
    a = poly { res };
  else
    for(int i=1; i<a.size(); ++i)
      a[i]+=res[i];
  return res;
}

bignum f(int n){
  std::vector<poly> dp;
  poly digits (10,1);
  poly dd { 1 };
  dp.push_back( dd );
  for(int i=1; i<n; ++i){
    dd=mult(dd,digits);
    int l=1+26*(n-i);
    if(dd.size()>l)
      dd.resize(l);
    dp.push_back(dd);
  }

  std::vector<std::vector<poly>> a;
  a.reserve(n);

  a.push_back( std::vector<poly> { poly { 0, 1 } } );
  for(int i=1; i<n; ++i)
    a.push_back( std::vector<poly> (1+std::min(i,n+i-i)));
  for(int m=n-1; m>0; --m){
    //    std::cout << "m=" << m << "\n";
    for(int sum=n-m; sum>=0; --sum)
      for(int len=0; len<=std::min(sum,n+1-sum); ++len){
        poly d {a[sum][len]} ;
        if(!d.empty())
          for(int sumn=sum+m, lenn=len+1, e=1;
              sumn+lenn-1<=n;
              sumn+=m, ++lenn, ++e)
            d=extend(d,dp[m],n-sumn,a[sumn][lenn],lenn,e);
      }
  }
  poly let (27,1);
  let[0]=0;
  poly lp { 1 };
  bignum t { 0 };
  for(int sum=n-1; sum>0; --sum){
    lp=mult(lp,let);
    for(int len=1; len<=std::min(sum,n+1-sum); ++len){
      poly &a0 = a[sum][len];
      bignum s {0};
      for(int i=1; i<std::min(a0.size(),lp.size()); ++i)
        s+=a0[i]*lp[i];
      bignum bin;
      mpz_bin_uiui( bin.get_mpz_t(), n-sum+1, len );
      t+=bin*s;
    }
  }
  return t;
}

int main(){
  int n;
  std::cin >> n;
  std::cout << f(n) << "\n" ;
}

Ini menggunakan perpustakaan MP GNU. Pada debian, instal libgmp-dev. Kompilasi dengan g++ -std=c++11 -O3 -o pl pl.cpp -lgmp -lgmpxx. Program mengambil argumennya dari stdin. Untuk penentuan waktu, gunakan echo 100 | time ./pl.

Pada akhirnya a[sum][length][i]berikan jumlah cara sum digit yang lengthberjalan dapat memberikan angka i. Selama perhitungan, pada awal mloop, ini memberikan jumlah cara yang bisa dilakukan dengan angka lebih besar dari m. Semuanya dimulai dengan a[0][0][1]=1. Perhatikan bahwa ini adalah superset dari angka yang kita perlukan untuk menghitung fungsi untuk nilai yang lebih kecil. Jadi pada saat yang hampir bersamaan, kita dapat menghitung semua nilai hingga n.

Tidak ada rekursi, jadi kami memiliki jumlah tetap dari loop bersarang. (Level sarang terdalam adalah 6.) Setiap loop melewati sejumlah nilai yang linear dalam nkasus terburuk. Jadi kita hanya perlu waktu polinomial. Jika kita melihat lebih dekat pada nested idan jloop extend, kita menemukan batas atas untuk jform N/i. Itu seharusnya hanya memberikan faktor logaritmik untuk jloop. Loop terdalam di f (dengan sumndll) serupa. Juga perlu diingat bahwa kami menghitung dengan angka yang tumbuh cepat.

Perhatikan juga bahwa kami menyimpan O(n^3)angka-angka ini.

Secara eksperimental, saya mendapatkan hasil ini pada perangkat keras yang wajar (i5-4590S): f(50)membutuhkan satu detik dan 23 MB, f(100)membutuhkan 21 detik dan 166 MB, f(200)perlu 10 menit dan 1,5 GB, dan f(300)perlu satu jam dan 5,6 GB. Ini menunjukkan kompleksitas waktu yang lebih baik daripada O(n^5).

Sievers Kristen
sumber
Karena ini adalah tantangan kode golf, jawaban ini perlu di- golf . Maaf.
Rɪᴋᴇʀ
1
@Riker Sementara saya tidak berpikir kode saya terlalu bertele-tele untuk memulainya, saya bermain golf lagi dan mengambil beban untuk menentukan ukurannya ketika ruang kosong diperas.
Christian Sievers
1
@cococuting Saya khawatir ini jauh lebih buruk. Saya menangani secara terpisah setiap kasus pendistribusian digit di antara deretan digit, seperti ada satu run dari tiga digit, atau ada satu run dari dua digit dan satu digit tunggal, atau ada tiga digit tunggal, tetapi untuk n=5, tidak ada kasus dengan menjalankan dua digit dan dua digit tunggal, karena dengan begitu kita tidak punya cukup surat untuk memisahkan angka. Inilah yang dilakukan tiga forloop luar : jalankan melalui semua partisi angka yang berguna<n . (Dan saya baru sadar saya juga mengizinkan nangka. Dengan sedikit keberuntungan optimasi lain dihitung sebagai 0).
Christian Sievers
1
@cococuting Perhatikan bahwa untuk angka <n/2, semua partisi berguna. Dan perhitungan yang tersisa masih membutuhkan waktu yang tidak konstan. Untuk melihat apa yang terjadi, Anda bisa menambahkan Print(p,"\n");di awal badan for p...loop. - Saya mendapat ide untuk menggunakan satu loop lebih sedikit, tetapi itu hanya akan membantu ukuran kode.
Christian Sievers
2
Saya mendapatkan kecepatan luar biasa dengan memindahkan mod(yang sudah banyak membantu) Value, mengubahnya menjadi Value(d mod x^(1+QuoInt(s(l)-1,i-1)),x^(i-1)). Itu saja memungkinkan untuk menghitung f(15)dalam 80 detik.
Christian Sievers
0

Pyth, 55 byte

FNQI<xrG1N0=+ZsN).?=+YZ=Z0;qu*G?HH1Y1sm?<xrG1d00hxrG1dQ
Karan Elangovan
sumber