Phân tích: Numbers

Bài toán với đề bài đơn giản này thực tế là một trong những bài khó nhất trong Vòng 1. Các hạn chế đầu vào cho tập dữ liệu nhỏ được chọn để các giải pháp đơn giản trong Java hoặc Python (vốn có số thực độ chính xác tùy ý) sẽ thất bại. Mẹo là tính \(\sqrt{5}\) với độ chính xác đủ lớn thay vì sử dụng giá trị double mặc định. Hóa ra việc sử dụng máy tính Windows hoặc công cụ bc của UNIX là đủ để giải các bộ test nhỏ.

Giải quyết các bộ test lớn là một vấn đề rất khác. Khó khăn đến từ việc \(\sqrt{5}\) là số vô tỉ và với \(n\) gần \(2000000000\), bạn sẽ cần rất nhiều độ chính xác và thời gian nếu muốn sử dụng giải pháp ngây thơ.

Chìa khóa để giải quyết vấn đề là một khái niệm toán học gọi là liên hợp. Trong bài toán này, chúng ta chỉ cần lưu ý rằng \((3 - \sqrt{5})\) là một liên hợp đẹp cho \((3 + \sqrt{5})\).
Hãy định nghĩa \(\alpha := 3 + \sqrt{5}\), \(\beta := 3 - \sqrt{5}\) và \(X_n := \alpha^n + \beta^n\).

Đầu tiên, chúng ta lưu ý rằng \(X_n\) là một số nguyên. Điều này có thể được chứng minh bằng cách sử dụng khai triển nhị thức. Nếu bạn viết mọi thứ ra, bạn sẽ nhận thấy rằng các số hạng vô tỉ của các tổng triệt tiêu lẫn nhau.

Một quan sát khác là \(\beta^n < 1\), vì vậy \(X_n\) thực chất là số nguyên đầu tiên lớn hơn \(\alpha^n\). Do đó, chúng ta chỉ cần tập trung vào việc tính ba chữ số cuối của \(X_n - 1\).

Lưu ý bên lề: Thực tế, \(\beta^n\) tiến tới 0 nhanh đến mức bài toán sẽ trở nên tầm thường nếu chúng ta hỏi ba chữ số sau dấu phẩy thập phân. Đối với tất cả các giá trị lớn của \(n\), chúng luôn là 999.

Dựa trên (1) và (2), có nhiều giải pháp khác nhau để tìm ba chữ số cuối của \(X_n\).

Giải pháp A. [Sự đan xen giữa số hữu tỉ và vô tỉ]

Một giải pháp như sau: \(\alpha^n\) có thể được viết dưới dạng \((a_n + b_n\sqrt{5})\), trong đó \(a_n\) và \(b_n\) là các số nguyên. Đồng thời, \(\beta^n\) chính xác là \((a_n - b_n\sqrt{5})\) và \(X_n = 2a_n\). Quan sát rằng \(\alpha^{n+1}=(3+\sqrt5)(a_n+b_n\sqrt5)=(3a_n+5b_n)+(3b_n+a_n)\sqrt5\).

Vì vậy \(a_{n + 1} = 3a_n + 5b_n\) và \(b_{n + 1} = 3b_n + a_n\). Điều này có thể được viết dưới dạng ma trận là:

Vì \(\alpha^0 = 1\), chúng ta có \((a_0, b_0) = (1, 0)\).
Bây giờ chúng ta sử dụng lũy thừa nhanh tiêu chuẩn để tính \(A^n\) trong thời gian \(O(\log n)\). Lưu ý rằng chúng ta thực hiện tất cả các phép tính theo modulo 1000 vì chúng ta chỉ cần trả về ba chữ số cuối của \(2a_n - 1\).

Dưới đây là mã Python triển khai giải pháp này:

def matrix_mult(A, B):
  C = [[0, 0], [0, 0]]
  for i in range(2):
    for j in range(2):
      for k in range(2):
        C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % 1000
  return C

def fast_exponentiation(A, n):
  if n == 1:
    return A
  else:
    if n % 2 == 0:
      A1 = fast_exponentiation(A, n/2)
      return matrix_mult(A1, A1)
    else:
      return matrix_mult(A, fast_exponentiation(A, n - 1))

def solve(n):
  A = [[3, 5], [1, 3]]
  A_n = fast_exponentiation(A, n)
  return (2 * M_n[0][0] + 999) % 1000

Giải pháp B. [Phương trình bậc hai và hệ thức truy hồi tuyến tính]

Các thí sinh có kinh nghiệm có thể nhận thấy có một hệ thức truy hồi tuyến tính trên các \(X_i\). Thật vậy, điều này không khó để tìm thấy -- phép liên hợp lại xuất hiện.
Lưu ý rằng \(\alpha+\beta=6\) và \(\alpha\beta=4\).

Vì vậy \(\alpha\) và \(\beta\) là hai nghiệm của phương trình bậc hai \(x^2 - 6x + 4 = 0\). Tức là \(\alpha^2=6\alpha-4\) và \(\beta^2=6\beta-4\).

Nhìn vào (1) và (6) cùng nhau, chúng ta có được \(X_{n+2}=6X_{n+1}-4X_n\).

Hệ thức truy hồi như vậy luôn có thể được viết dưới dạng ma trận:

Từ đây lại là một phép lũy thừa ma trận nhanh. Hãy xem mã Perl của radeye triển khai cách tiếp cận này:

sub mul {
    my $a = shift ;
    my $b = shift ;
    my @a = @{$a} ;
    my @b = @{$b} ;
    my @c = ($a[0]*$b[0] + $a[1]*$b[2],
             $a[0]*$b[1] + $a[1]*$b[3],
             $a[2]*$b[0] + $a[3]*$b[2],
             $a[2]*$b[1] + $a[3]*$b[3]) ;
    @c = map { $_ % 1000 } @c ;
    return @c ;
}
sub f {
    my $n = shift ;
    return 2 if $n == 0 ;
    return 6 if $n == 1 ;
    return 28 if $n == 2 ;
    $n -= 2 ;
    my @mat = (0, 1, 996, 6) ;
    my @smat = @mat ;
    while ($n > 0) {
        if ($n & 1) {
            @mat = mul([@mat], [@smat]) ;
        }
        @smat = mul([@smat], [@smat]) ;
        $n >>= 1 ;
    }
    return ($mat[0] * 6 + $mat[1] * 28) % 1000 ;
}
sub ff {
   my $r = shift ;
   $r = ($r + 999) % 1000 ;
   $r = "0" . $r while length($r) < 3 ;
   return $r ;
}
for $c (1..<>) {
    $n = <> ;
    print "Case #$c: ", ff(f($n)), "\n" ;
}

Giải pháp C. [Tính chu kỳ của 3 chữ số cuối]

Đối với bài toán này, chúng ta có một cách tiếp cận khác dựa trên hệ thức truy hồi (7). Lưu ý rằng chúng ta chỉ cần tập trung vào 3 chữ số cuối của \(X_n\), vốn chỉ phụ thuộc vào 3 chữ số cuối của hai số hạng trước đó. Các số cuối cùng sẽ trở nên tuần hoàn ngay khi chúng ta có \((X_i, X_{i+1})\) và \((X_j, X_{j+1})\) có cùng 3 chữ số cuối, với \(i < j\). Rõ ràng là chúng ta sẽ bước vào một chu kỳ không muộn hơn \(10^6\) bước.
Thực tế, đối với bài toán này, bạn có thể viết mã và thấy rằng chu kỳ có kích thước 100 và bắt đầu từ phần tử thứ 3 trong dãy. Vì vậy, để giải bài toán, chúng ta có thể tính trâu kết quả cho 103 số đầu tiên và nếu \(n\) lớn hơn 103, trả về kết quả được tính cho số \((n - 3) \pmod{100} + 3\).

Giải pháp D. [Truy tìm thuần túy về số học và tổ hợp]

Hãy xem thêm một giải pháp mang hương vị khác. Đây là một giải pháp không tổng quát như những giải pháp khác, nhưng được thiết kế riêng cho bài toán này, khiến chúng ta cảm thấy như đang giải bài toán này bằng tay.

Hãy nhìn lại (2). Chúng ta muốn biết \(X_n \pmod{1000}\). Chúng ta biết từ định lý số dư Trung Hoa rằng nếu chúng ta có thể tìm được \(X_n \pmod 8\) và \(X_n \pmod{125}\), thì \(X_n \pmod{1000}\) sẽ được xác định duy nhất.

(a) Với \(n > 2\), \(X_n \pmod 8\) luôn bằng 0. Vì \(5^i \equiv 1 \pmod 4\), \(3^{n-2i} \equiv 1\) hoặc \(-1 \pmod 4\) tùy thuộc vào \(n\), nên với \(n > 2\):

(b) Để tính \(X_n \pmod{125}\), chúng ta chỉ cần lo lắng về \(i=0,1,2\). Tất cả các phần còn lại đều bằng \(0 \pmod{125}\). Nói cách khác, tất cả những gì chúng ta cần tính là:

Có nhiều cách khác nhau để tính các thành phần trong biểu thức trên. Các lũy thừa có thể được tính bằng lũy thừa nhanh, hoặc sử dụng thực tế là \(3^n \pmod{125}\) tuần hoàn với độ dài chu kỳ tối đa là 124. Các số nhị thức có thể được tính bằng cách sử dụng số nguyên độ chính xác tùy ý trong các ngôn ngữ như Java và Python, hoặc lập trình cẩn thận một chút trong các ngôn ngữ như C++.

Dựa trên phân tích chính thức của Google Code Jam.