TGPASCAL

View as PDF
Submit solution
Points: 0.44 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem source:
thi hsg
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 4
    pppssslc  commented on June 26, 2025, 3:49 a.m. ← edited

    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  commented on July 15, 2025, 1:05 p.m.

      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  commented on July 15, 2025, 1:17 p.m. ← edited

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


  • 0
    maiphucthinhpika34  commented on May 11, 2025, 9:02 a.m.

    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)