CSES - Two Sets II | Hai tập hợp II

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
NguyenHuuNhatQuang , Flower_On_Stone , kitsune
Dạng bài
Điểm: 1600 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Hãy đếm số cách mà các số \(1, 2,\ldots,n\) có thể được chia thành hai tập hợp có tổng bằng nhau.

Ví dụ, với \(n = 7\), có \(4\) cách chia:

  • \(\{1,3,4,6\}\) và \(\{2,5,7\}\)
  • \(\{1,2,5,6\}\) và \(\{3,4,7\}\)
  • \(\{1,2,4,7\}\) và \(\{3,5,6\}\)
  • \(\{1,6,7\}\) và \(\{2,3,4,5\}\)

Input

  • Gồm một dòng duy nhất chứa số nguyên \(n\).

Output

  • In đáp án - số cách thoả mãn chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

  • \(1 \leq n \leq 500\)

Example

Sample input

7

Sample output

4

Bình luận


  • 0
    rock    8:10 a.m. 25 Tháng 10, 2024

    var n,i,j,m:longint;
    d:array[0..100001] of int64;
    BEGIN
    readln(n);
    d[0]:=1;
    if n(n+1) div 2 mod 2 = 1 then write('0') else
    begin
    m:=n    (n+1) div 4;
    for i:=1 to n do
    for j:=m downto i do
    d[j]:=(d[j]+d[j-i]) mod 1000000007;
    write(d[m]*1000000008 div 2 mod 1000000007);
    end;
    END.

      • 1 bình luận nữa