TGPASCAL

Xem dạng PDF
Gửi bài giải
Điểm: 0,44 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Nguồn bài:
thi hsg
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong toán học, tam giác Pascal là một mảng tam giác của hệ số nhị thức trong tam giác. Thuật toán được đặt theo tên của nhà toán học Pháp nổi tiếng Blaise Pascal

Trong tam giác số này, bắt đầu từ hàng thứ hai, mỗi số ở hàng thứ ~n~ từ cột thứ hai đến cột ~n - 1~ bằng tổng hai số đứng ở hàng trên cùng cột và cột trước nó. Sở dĩ có quan hệ này là do có công thức truy hồi:

~C_{n} ^ k = C_{n - 1} ^ {k - 1} + C_{n - 1} ^ k~ ~(1 < k < n)~

Một hình ảnh về tam giác pascal

image

Yêu cầu xác định số các số lẻ nằm trên dòng thứ N của tam giác pascal, quy ước đánh số dòng bắt đầu từ 0

Input

Một số dương ~N~ ~(1 \leq N \leq 10^{9})~

Output

Số các số lẻ nằm trên dòng thứ ~N~

Sample Input

5

Sample Output

4

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 0
    ijk  đã bình luận lúc 28, Tháng 6, 2026, 10:44

    Sau một hồi suy nghĩ vì sao giải thuật của pppssslc đúng thì mình đã chứng minh xong, dành cho ae để không phải chứng minh lại

    Theo định lý Lucas, ~C_n^k \equiv C_{n_1}^{k_1}C_{n_2}^{k_2}...C_{n_p}^{k_p} \pmod{m}~ với ~m~ là số nguyên tố, ~n_i, k_i~ là biểu diễn theo cơ số ~m~

    Bài toán đang xét tính chẵn lẻ của ~C_n^k~ nên ta lấy ~m=2~

    Từ đó suy ra ~k_i, n_i \in {0;1}~ hay nói cách khác là biểu diễn nhị phân của ~k~ và ~n~

    Nhận thấy để ~C_n^k~ lẻ thì bit thứ ~i~ của ~n~ phải lớn hơn hoặc bằng bit thứ i của ~k~

    Gọi ~n_i~ là bit thứ ~i~ của ~n~. Nếu ~n_i=0~, ta chỉ có một cách xếp bit thứ ~i~ của ~k~ vào vị trí đó chính là xếp số ~0~ vào. Tương tự với ~n_i=1~, ta có thể xếp 0 hoặc 1 tùy ý.

    Theo quy tắc nhân, chúng ta sẽ có ~2^x~ giá trị ~k~ thỏa mãn (với ~x~ là số lượng bit 1 trong ~n~).

    Hy vọng bài chứng minh sẽ giúp ae hiểu được bài toán và không cop code <(")


  • 4
    pppssslc  đã bình luận lúc 26, Tháng 6, 2025, 3:49 ← chỉnh sửa

    My solve:

    Hint:

    Số lượng số lẻ ở tầng thứ ~n~ của tam giác pascal là ~2 ^ {s(n)}~ với ~s(n)~ là số lượng bit ~1~ trong biểu diễn nhị phân của ~n~.

    Code mẫu C++:

    #include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    cout << (1 << __builtin_popcount(n));
    return 0;
}

    • 0
      feedupcoder  đã bình luận lúc 15, Tháng 7, 2025, 13:05

      Cảm ơn cậu nhá. Nhưng mà cho mình hỏi chút có chứng minh được không cậu.


      • 1
        pppssslc  đã bình luận lúc 15, Tháng 7, 2025, 13:17 ← chỉnh sửa

        Có nha, theo mình tìm hiểu là sử dụng định lí Lucas.


  • 0
    maiphucthinhpika34  đã bình luận lúc 11, Tháng 5, 2025, 9:02

    def countoddnumbersinpascal_row(n): # Chuyển đổi N sang nhị phân và đếm số lượng 1 b = bin(n).count('1') # Tính số lượng số lẻ return 2 ** b

    Đọc số hàng N

    n = int(input()) oddcount = countoddnumbersinpascalrow(n) print(odd_count)