Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán rời rạc] Giá trị đa thức sắc tại k

    Đa thức sắc P(G,k)P(G,k)P(G,k) của đồ thị GGG cho biết số cách tô đúng các đỉnh bằng kkk màu sao cho hai đỉnh kề khác màu. Nó thỏa hệ thức xóa–co (deletion–contraction):

    P(G,k)=P(G−e,k)−P(G/e,k).P(G,k)=P(G-e,k)-P(G/e,k).P(G,k)=P(G−e,k)−P(G/e,k).

    Cho đồ thị nhỏ và số màu kkk, hãy tính P(G,k)P(G,k)P(G,k). Kết quả vừa với số nguyên 64-bit, không cần modulo.

    • Định dạng đầu vào:

      Dòng đầu: nnn, mmm, kkk. mmm dòng sau mỗi dòng một cạnh u vu\ vu v (0≤u,v<n0\le u,v<n0≤u,v<n).

    • Ràng buộc đầu vào:

      1≤n≤121 \le n \le 121≤n≤12, 0≤m≤n(n−1)/20 \le m \le n(n-1)/20≤m≤n(n−1)/2, 1≤k≤1001 \le k \le 1001≤k≤100, không cạnh lặp/khuyên.

    • Định dạng đầu ra:

      Một dòng: số cách tô đúng GGG bằng kkk màu.

    Ví dụ:

    Đầu vào:

    3 3 3
0 1
1 2
0 2

    Đầu ra:

    6

    Giải thích:

    $P(K_3,3)=3\cdot 2\cdot 1=6$ cách tô đúng tam giác bằng 3 màu.

    Đang tải editor...